SPOJ in Gyumri

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

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

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

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

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

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

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

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

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

Пример.