Кратчайший путь

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

Первая строка - количество городов и дорог через пробел (городов не более 1000).

Далее следуют описания дорог: номера городов, соединённых дорогой и расстояние - всего три числа через пробел (расстояние не более миллиарда).

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

Расстояние от первого города до последнего.

Гарантированно, что путь всегда найдётся.

Пример

input             output

5 6                8  

1 2 1

2 3 6

3 5 1

1 4 3

4 5 6

1 5 12