该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

借光

题目描述

有一张无向图，包含 $n$ 个路口和 $m$ 条道路。每条道路都有一种颜色。

你有一盏灯。开始时，灯没有颜色。

如果要经过一条颜色为 $c$ 的道路：

• 若灯当前就是颜色 $c$，可以直接通过，代价为 $0$；
• 否则，需要先把灯调成颜色 $c$，代价为 $1$，然后通过这条道路。

通过道路后，灯的颜色仍然是这条道路的颜色。

请你求从路口 $1$ 到路口 $n$ 的最小总代价。

如果无法从路口 $1$ 到达路口 $n$，输出 $-1$。

输入格式

第一行输入两个整数 $n,m$，表示路口数量和道路数量。

接下来 $m$ 行，每行输入三个整数 $u,v,c$，表示一条连接路口 $u$ 和路口 $v$、颜色为 $c$ 的无向道路。

图中可能存在重边，但不含自环。

数据范围

对于所有测试数据，保证：

所有输入数据均为整数。

当 $n=1$ 时，起点已经是终点，答案为 $0$。

输出格式

输出一个整数，表示从路口 $1$ 到路口 $n$ 的最小总代价。

如果无法到达，输出 $-1$。

输入输出样例 #1

输入 #1

5 5
1 2 1
2 5 2
1 3 3
3 4 3
4 5 3

输出 #1

1

输入输出样例 #2

输入 #2

4 2
1 2 7
3 4 7

输出 #2

-1

输入输出样例 #3

输入 #3

1 0

输出 #3

0

说明/提示

对于样例 #1，可以走：

1 -> 3 -> 4 -> 5

三条道路颜色都是 $3$，只需要一开始把灯调成颜色 $3$，总代价为 $1$。

对于样例 #2，虽然两条道路颜色相同，但颜色相同不代表可以跨连通块移动，因此无法从路口 $1$ 到达路口 $4$。

对于样例 #3，起点已经是终点，不需要移动，答案为 $0$。