Գտնել կարճագույն ուղին 3
Ձեզ տրված է մի քարտեզ, որը կազմված է
n քաղաքներից և այդ քաղաքները կապող m երկկողմանի ճանապարհներից։ Յուրաքանչյուր ճանապարհ ունի ոչ բացասական ամբողջ թվային երկարություն, որը խորհրդանշված է -ով։ Ձեր առաջադրանքն է որոշել, թե ինչքան է ամենակարճ ճանապարհի երկարությունը քաղաք 1-ից մինչև քաղաք n։Մուտք
Մուտքի առաջին տողում տրված են երկու ամբողջ числа
n և m ($2 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^5$), որոնք ներկայացնում են քաղաքների և ճանապարհների քանակը, համապատասխանաբար։Հաջորդ
m տողերից յուրաքանչյուրում տրված են երեք ամբողջ числа , և , որոնք նկարագրում են մեկ ճանապարհ քաղաք -ի և քաղաք -ի միջև,having a length of ($1 ≤ ui, vi ≤ n, 1 ≤ w_i ≤ 10^9$):Ելք
Տպեք մեկ ամբողջ թիվ, որը ցույց է տալիս ամենակարճ ճանապարհի երկարությունը քաղաք
1-ից մինչև քաղաք n։Օրինակներ
Մուտք | Ելք |
4 5
1 2 3
1 3 5
2 4 3
3 4 3
1 4 7 | 6 |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB