Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

GML0564 - РОЛЕВАЯ ИГРА

   Вовочка с друзьями придумал очень интересную игру. Из играющих выбирается один человек, и он получает роль «Сусанина». Оставшиеся игроки получают роль «Поляков». Задача «Сусанина» завести «Поляков» в такое место в лесу из которого «Поляки» не смогут найти обратной дороги. После того как «Поляки» признают, что это именно то место, задача «Сусанина» показать своё мастерство и вывести всех из леса.

   Вовочке досталась роль «Сусанина». Перед игрой Вовочка составил карту леса. На карте он обозначил N полянок соединённых между собой M тропинками.

   С первой задачей игры Вовочка справился отлично. Теперь его задача вывести всех из леса. Согласно предположениям Вовочки они находятся на полянке с номером N. Для того чтобы выбраться, им необходимо добраться до полянки с номером 1.

   Ваша задача помочь Вовочке определить длину кратчайшего пути от полянки с номером N до полянки с номером 1.

Входные данные.

   В первой строке находятся числа N и M. Далее следует M строк, в каждой из которой три числа — номера полянок, которые соединяет тропинка, и третье число — длина этой тропинки.

   Все числа кроме M целые и не превосходят 1000. M — целое и не превосходит 10000.

Выходные данные.

   Одно число — длина кратчайшего пути. Гарантируется что путь всегда существует.

Пример.

N

stdin

stdout

1

3 4
1 3 10
1 2 5
3 2 4
2 1 6

9


Ավելացրեց.Հրանտ Հովհաննիսյան
Ամսաթիվ.2016-08-29
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PYPY3 PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE
Աղբյուրը.Գոմել: Ավագ տարիքային խումբ:

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.