Երկրորդ ամենակարճ ուղի

Ձեզ տրվել են n քաղաքներ և m երկկողմանի ճանապարհներ, որոնք կապում են դրանք: Յուրաքանչյուր ճանապարհ ունի համապատասխան երկարություն : Արկածախնդիր ճամփորդ Emil-ը ցանկանում է քաղաք 1-ից հասնել քաղաք n այդ ճանապարհներով: Սակայն նա որոշել է ընտրել այն ուղին, որը ամենակարճն է բոլոր այն ուղիներից, որոնք խիստ երկար են ամենակարճ ընդհանուր ուղուց:

Այլ կերպ ասած, ձեր նպատակը βοηել Emil-ին որոշելու քաղաք 1-ից քաղաք n հասնող երկրորդ ամենակարճ ուղու երկարությունը:

Մուտք

Մուտքի առաջին տողում տրված են երկու ամբողջ թիվ n և m, որոնք ցույց են տալիս քաղաքների և ճանապարհների քանակը, համապատասխանաբար:
Հաջորդ m տողերում տրված են երեք ամբողջ թվեր , և , որոնք սահմանում են, որ կա երկկողմանի ճանապարհ քաղաք -ի և քաղաք -ի միջև երկարությամբ:

Ելք

Ելքում պետք է տպել մեկ ամբողջ թիվ, որը ներկայացնում է երկրորդ ամենակարճ ուղու երկարությունը քաղաք 1-ից քաղաք n հասնելու համար:

Օրինակներ

Մուտք

Ելք

6 7
1 2 3
2 3 4
3 6 5
2 6 9
1 4 3
4 5 8
5 6 2

13

Constraints

Time limit: 5.4 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue