Երկրորդ ամենակարճ ուղի
Ձեզ տրվել են
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