Գտիր ամենակարճ ճանապարհը 1
Ձեզ տրված է քարտեզ, որը բաղկացած է
n քաղաքներից և m երկկողմանի ճանապարհներից: Յուրաքանչյուր ճանապարհ ունի ոչ բացասական ամբողջ երկարություն, որը նշվում է : Ձեր խնդիրը պարզելն է, թե ինչ երկարություն ունի ամենակարճ ճանապարհը քաղաք 1-ից քաղաք n:Մուտք
Մուտքի առաջին տողում մեկ բացատով բաժանված տրվում են
n և m ամբողջ թվերը (), որոնք նշում են համապատասխանաբար քաղաքների քանակը և ճանապարհների քանակը:Հաջորդ
m տողերից յուրաքանչյուրում մեկ բացատով բաժանված տրվում են երեք ամբողջ թվեր , և , որոնք ներկայացնում են ճանապարհ և քաղաքների միջև, որի երկարությունը է ():Ելք
Ծրագիրը ելքում պետք է տպի ամենակարճ ճանապարհի երկարությունը քաղաք
1-ից քաղաք n:Օրինակներ
Մուտք | Ելք |
4 5
1 2 3
1 3 5
2 4 3
3 4 3
1 4 7 | 6 |
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB