题目描述

Snuke 居住的城市有一套地铁系统，由 $N$ 个车站和 $M$ 条地铁线路组成。车站的编号为 $1$ 到 $N$。每条线路都由某家公司运营，每家公司有一个公司编号。

第 $i$ 条线路（$1 \le i \le M$）双向连接车站 $p_i$ 和 $q_i$。该线路没有中间站，其运营公司为 $c_i$。

若一个车站有多条线路经过，则乘客可以在该站换乘。

这个城市的计费方式比较奇怪：

• 若乘客全程只使用同一家公司的线路，则费用为 $1$ 日元。
• 若乘客从公司 $A$ 的线路换乘到另一家公司的线路，则需要额外支付 $1$ 日元。
• 若乘客从公司 $A$ 换乘到公司 $B$ 后，又换回公司 $A$，仍然需要再次支付额外的 $1$ 日元。

Snuke 现在位于车站 $1$，想要乘坐地铁到达车站 $N$。请你求出到达车站 $N$ 所需支付的最少费用。

输入格式

输入从标准输入读入，格式如下：

N M
p_1 q_1 c_1
...
p_M q_M c_M

输出格式

输出从车站 $1$ 到车站 $N$ 所需支付的最小费用。

如果无法通过地铁到达车站 $N$，输出 $-1$。

样例 1

3 3
1 2 1
2 3 1
3 1 2

1

使用公司 $1$ 的线路：$1 \to 2 \to 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 \to 3 \to 2 \to 5 \to 6$
• 再换乘到公司 $5$ 的线路：$6 \to 7 \to 8$

总费用为 $2$ 日元。

样例 3

2 0

-1

数据范围

• 存在$30\%$ 的数据，$2 \le n \le 1000, 0 \le m \le 1000$

• 另外 $30\%$ 的数据，$1\le c_i \le 1000$

• $100\%$的数据,$2 \le N \le 10^5$，$0 \le M \le 2 \times 10^5$ ， $1 \le p_i, q_i \le N$ ， $1 \le c_i \le 10^6$，$p_i \ne q_i$