Mr.Quin love fishes so much and Mr.Quin’s city has a nautical system,consisiting of $$$N$$$ ports and $$$M$$$ shipping lines. The ports are numbered $$$1$$$ to $$$N$$$. Each line is occupied by a Weitian. Each Weitian has an identification number.
The $$$i$$$-th $$$(1 \leq i \le M)$$$ line connects port $$$A_i$$$ and $$$B_i$$$ $$$(A_i \ne B_i )$$$ bidirectionally, and occupied by $$$C_i$$$ Weitian (At most one line between two ports).
When Mr.Quin only uses lines that are occupied by the same Weitian, the cost is $$$1$$$ XiangXiangJi. Whenever Mr.Quin changes to a line that is occupied by a different Weitian from the current line, Mr.Quin is charged an additional cost of $$$1$$$ XiangXiangJi. In a case where Mr.Quin changed from some Weitian $$$A$$$'s line to another Weitian's line changes to Weitian $$$A$$$'s line again, the additional cost is incurred again.
Mr.Quin is now at port $$$1$$$ and wants to travel to port $$$N$$$ where live many fishes. Find the minimum required XiangXiangJi (If Mr.Quin can’t travel to port $$$N$$$, print $$$-1$$$ instead)
There might be multiple test cases, no more than $$$20$$$. You need to read till the end of input.
For each test case,In the first line, two integers $$$N$$$ $$$(2 \le N \le 100000)$$$ and $$$M$$$ $$$(0 \le M \le 200000)$$$, representing the number of ports and shipping lines in the city.
In the following m lines, each contain three integers, the first and second representing two ends $$$A_i$$$ and $$$B_i$$$ of a shipping line $$$(1 \le A_i, B_i \le N)$$$ and the third representing the identification number $$$C_i$$$ $$$(1 \le C_i \le 1000000)$$$ of Weitian who occupies this shipping line.
For each test case output the minimum required cost. If Mr.Quin can’t travel to port $$$N$$$, output $$$-1$$$ instead.
1 2 1
1 3 2
2 3 1
1 2 1
2 3 2