Ալգորիթմներ և Տվյալների Կառուցվածքներ

Գտնել ամենակարճ ուղին 2

Ձեզ խնդրում են գրել ծրագիր, որը ստանալով n քաղաքներից և m երկկողմանի ճանապարհներից բաղկացած քարտեզ, որտեղ յուրաքանչյուր ճանապարհի երկարությունը ոչ-բացասական ամբողջ թիվ է (), պետք է որոշի ամենակարճ երթուղու llargությունը քաղաք 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: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

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