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.