Ослиный вопль 
Input file: 	HOWL.IN			
Output file: HOWL.OUT			Time limit: 1 sec.

В саду у маленького Ослика Ио-Ио растут N кустов прекрасных рододендронов, и ослик очень любит бегать по саду. Некоторые пары кустов рододендронов соединены тропинками, всего в саду имеется M тропинок. Конечно, тропинки где-то пересекаются, но Ослик Ио-Ио переходит с одной тропинки на другую только возле куста. Потом к нему приехал сельский родственник Осёл I.A., и тут такое началось... В общем, вы помните...

Новая беда  - теперь Осёл I.A. тоже решил бегать по саду. Он хочет, чтобы его маршрут начинался возле куста номер 1 и заканчивался возле куста номер N. Других пожеланий у него нет. Впрочем, он обещает переходить с тропинки на тропинку только возле куста.

Беда в том, что ровно посередине каждой пробегаемой тропинки Осёл I.A. издаёт неимоверной скрипучести ослиный вопль. Звуки в саду распространяются неравномерно, и из разных мест сада вопль Осла доносится до домика Ослика Ио-Ио с разной громкостью. Точнее говоря, для каждой тропинки известна громкость, с которой вопль Осла доносится до домика.

Маленький Ослик Ио-Ио хочет, чтобы самый громкий вопль был слышен в домике как можно слабее. Для этого он хочет проложить такой маршрут от куста номер 1 до куста номер N, что самый громкий вопль, который издаст Осёл I.A. во время пробежки, был слышен как можно слабее. 

Помогите несчастному Ослику. Определите минимальную возможную громкость самого громкого вопля, который донесётся до него поутру.
 
Входные данные. В первой строке входного файла находятся два натуральных числа: N, 1<=N<=1000, и M, 1<=M<=100000. Кусты рододендронов пронумерованы числами от 1 до N.
Каждая из следующих M строк содержит описание одной тропинки – три натуральных числа, разделённых пробелами: первые два числа – это номера кустов, соединяемые тропинкой, третье число – громкость вопля, слышная в домике. Все громкости не превосходят 100000000.
Гарантируется, что 
•	имеется хотя бы один маршрут от куста номер 1 до куста номер N;
•	любые два куста соединены не более, чем одной тропинкой.
 
Выходные данные. В единственной строке следует выводить одно натуральное число - минимальная возможная громкость самого громкого вопля, который донесётся до домика во время пробежки Осла I.A.

Примеры 	HOWL.IN			HOWL.OUT	   	Примечание
4 5  			4			Наилучший маршрут: 1-3-2-4
1 2 5						
2 4 4
4 3 9
3 2 2
1 3 3

HOWL.IN			HOWL.OUT		Примечание.
3 3  			8			Наилучший маршрут: 1-2-3
3 1 9
3 2 8
1 2 3