题目描述

Snuke的城镇有地铁行驶，地铁线路图包括 $N$ 个站点和 $M$ 个地铁线。站点被从 $1$ 到 $N$ 的整数所标记，每条线路被一个公司所拥有，并且每个公司用彼此不同的整数来表示。

第 $i$ 条线路( $1≤i≤M$ )是直接连接 $p_i$ 与 $q_i$ 的双向铁路，中间不存在其他站点，且这条铁路由 $c_i$ 公司所拥有。

如果乘客只乘坐同一公司的铁路，他只需要花费一元，但如果更换其他公司的铁路需要再花一元。当然，如果你要再换回原来的公司，你还是要花一元。

Snuke在1号站的位置出发，他想通过地铁去第 $N$ 站，请求出最小钱数。如果无法到达第 $N$ 站，输出-1。

输入格式

第一行，输入 $N$ , $M$

接下来的 $M$ 行，输入 $p_i$ $q_i$ $c_i$ ，代表 $p_i$ 与 $q_i$ 中间有直接连接的双向边，且这条铁路由 $c_i$ 公司所拥有。

输出格式

输出最小钱数（若无法到达，输出-1）

感谢@SaltedHXJ 提供的翻译

样例 1

输入

3 3
1 2 1
2 3 1
3 1 2

输出

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

样例 3

输入

2 0

输出

-1

说明/提示

数据范围

• $2 \leq N \leq 10^5$
• $0 \leq M \leq 2×10^5$
• $1 \leq p_i \leq N$ $(1 \leq i \leq M)$
• $1 \leq q_i \leq N$ $(1 \leq i \leq M)$
• $1 \leq c_i \leq 10^6$ $(1 \leq i \leq M)$
• $p_i \neq q_i$ $(1 \leq i \leq M)$