题目描述

算法协会在一座有 $n$ 个房间的建筑中举办寻路游戏。房间编号为 $1$ 到 $n$，房间之间有 $m$ 条双向通道。每条通道的颜色为红色或蓝色，分别用 $0$ 和 $1$ 表示。

你拥有一张可以变色的通行证。通行证在任意时刻也是红色或蓝色。移动规则如下：

1. 只有当通道的颜色与通行证的当前颜色相同时，才能通过这条通道。

2. 每次通过一条通道后，通行证立即变为另一种颜色。

3. 每次通过一条通道消耗 $1$ 分钟。

游戏开始时，你位于房间 $1$，可以自由选择通行证的初始颜色。此后，通行证只能通过上述移动规则变色，停留不会使其变色。你可以重复经过房间和通道。

请计算从房间 $1$ 到达房间 $n$ 至少需要多少分钟。到达房间 $n$ 时，通行证可以是任意颜色。如果无法到达，输出 $-1$。如果起点就是终点，则所需时间为 $0$。

输入格式

第一行包含一个整数 $t$（$1\le t\le10^{4}$），表示测试用例的数量。

对于每个测试用例：

• 第一行包含两个整数 $n,m$（$1\le n\le2\times10^{5}$，$0\le m\le2\times10^{5}$），分别表示房间的数量和通道的数量。

• 接下来 $m$ 行，每行包含三个整数 $u,v,c$（$1\le u,v\le n$，$u\ne v$，$c\in\{0,1\}$），表示房间 $u$ 和房间 $v$ 之间有一条颜色为 $c$ 的双向通道。

保证任意两个不同的房间之间至多有一条通道。所有测试用例的 $n$ 之和不超过 $2\times10^{5}$，$m$ 之和不超过 $2\times10^{5}$。

输出格式

对于每个测试用例，输出一行一个整数，表示从房间 $1$ 到达房间 $n$ 至少需要的分钟数。如果无法到达，输出 $-1$。

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

4
-1
0

样例解释

第一组测试用例中，选择蓝色作为通行证的初始颜色，可以沿路线

$$1\xrightarrow{1}3\xrightarrow{0}4\xrightarrow{1}2\xrightarrow{0}5$$

到达终点。箭头上方的数字表示通道颜色，总共需要 $4$ 分钟。

路线 $1\rightarrow2\rightarrow5$ 的两条通道均为红色。通过第一条通道后，通行证变为蓝色，无法立即通过第二条通道。

第二组测试用例中，两条通道均为红色，无法按照规则到达房间 $3$，答案为 $-1$。

第三组测试用例中，起点就是终点，答案为 $0$。