Давилон - самый крупный город на Луне. На Давилоне есть собственная система метро, состоящая из N станций и M железнодорожных линий. Станции пронумерованы от 1 до N. Каждой линией управляет компания. У каждой компании есть идентификационный номер. I-я (1<=i<=M) линия соединяет станцию pi и qi двунаправленно. Промежуточной станции нет. Этой линией управляет компания ci . Можно делать пересадки на станции, где доступно несколько линий. Система оплаты проезда, используемая в этой системе метро, немного странная. Когда пассажир использует только те линии, которые обслуживаются одной и той же компанией, тариф составляет 1 сантик (валюта Давилона). Каждый раз, когда пассажир переходит на линию, которой управляет компания, отличная от текущей линии, с пассажира взимается дополнительная плата за проезд в размере 1 сантик. В случае, если пассажир, перешедший с линии компании А на линию другой компании, снова переходит на линию компании А, дополнительный тариф взимается снова. Незнайка сейчас на станции 1 и хочет добраться до станции N на метро. Найдите минимально необходимый тариф.
Входные данные
В первой строке задается два целых числа N (2<=N<=10
5) и M (0<=M<=2*10
5). В каждой из следующих M строк записаны по 3 числа: pi, qi и ci; 1<=pi<=N (1<=i<=M), 1<=qi<=N, 1<=ci<=10
6, pi ≠ qi.
Выходные данные
Выведите минимальный требуемый тариф. Если добраться до станции N на метро невозможно, выведите
-1.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
3 3
1 2 1
2 3 1
3 1 2 |
1 |
Используйте линии компании 1:
1 → 2 → 3.
Стоимость проезда 1 сантик. |
| 2 |
8 11
1 3 1
1 4 2
2 3 1
2 5 1
3 4 3
3 6 3
3 7 3
4 8 4
5 6 1
6 7 5
7 8 5 |
2 |
Сначала используйте линии компании 1:
1 → 3 → 2 → 5 → 6.
Затем используйте линии компании 5:
6 → 7 → 8.
Стоимость проезда 2 сантика. |
| 3 |
2 0 |
-1 |
|