Davilon is the largest city on the moon. Davilon has its own metro system, consisting of N stations and M railway lines. The stations are numbered from 1 to N. Each line is operated by a company. Each company has an identification number. The ith (1<=i<=M) line connects station pi and qi bidirectionally. There is no intermediate station. This line is run by ci. You can transfer at stations where there are several lines available. The fare system used in this subway system is a bit odd. When a passenger uses only those lines operated by the same company, the fare is 1 santik (the currency of Davilon). Each time a passenger transfers to a line operated by a company other than the current line, the passenger will be charged an additional fare of 1 centik. In the event that a passenger who switched from the line of company A to the line of another company switches again to the line of company A, the additional fare is charged again. Dunno is now at station 1 and wants to get to station N by metro. Find the minimum required rate.
Input
The first line contains two integers N (2<=N<=10
5) and M (0<=M<=2*10
5). Each of the next M lines contains 3 numbers: pi, qi and ci; 1<=pi<=N (1<=i<=M), 1<=qi<=N, 1<=ci<=10
6, pi ≠ qi.
Imprint
Output the minimum required rate. If it is impossible to get to station N by metro, print
-1.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
3 3
1 2 1
2 3 1
3 1 2
| 1 |
Use company lines 1:
1 &rr; 2 &rr; 3.
The fare is 1 cent. |
| 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 |
Use company lines first:
1 &rr; 3 &rr; 2 &rr; 5 &rr; 6.
Then use company lines 5:
6 &rr; 7 &rr; 8.
The fare is 2 cents. |
| 3 |
2 0 |
-1 |
|