SPOJ in Gyumri

   Часто летом родители отвозят Вовочку отдохнуть в деревню к бабушке. Вовочке очень нравится там бывать. Причина этого кроется в бабушкином доме. Это очень старый дом и построен он по забытым ныне технологиям. Весь дом собой представляет N комнат. Переходы между комнатами представляют собой туннели, вырытые под землёй. Причем они вырыты все на разной глубине и поэтому не пересекаются.

   Вовочке удалось составить план этого необычного домика. И вот сейчас ему интересно узнать какое минимальное расстояние необходимо преодолеть, чтобы добраться от прихожей (комната номер 1) до бабушкиной комнаты (комната N).

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

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

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

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

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

Пример.