题目描述

在艾泽拉大陆上，有$n$个被遗忘的遗迹。

冒险者小$S$得知，在编号为 $n$ 的遗迹中藏有传说中的宝藏，因此他决定从$1$号遗迹出发，前往$n$号遗迹。

大陆上有$m$个传送门，每个传送门连接两个遗迹，并且可以双向通行。每个传送门属于一个魔法协会。

小$S$可以向魔法协会支付一枚金币，使用该协会的传送门进行传送。在连续的传送中，若小$S$使用的都是同一个协会的传送门，则只需要支付一枚金币。若小$S$使用另一个协会的传送门，则需要重新支付一枚金币。

例如：小$S$通过$A$协会传送门到达某个遗迹，然后使用$B$协会传送门前往下一个遗迹，则小$S$需要向$B$协会支付一枚金币，若小S之后想重新使用$A$协会传送门，则还需向$A$协会支付金币。

请帮助小$S$设计一条传送路线，使得他从$1$号遗迹到$n$号遗迹需要支付的金币数量最少，并输出这个最小金币数。保证可以从1号遗迹到$n$号遗迹。

输入格式

第一行输入一个整数 $T$（$1 \le T \le 10$），表示测试的总数。

第二行包含两个整数 $n$ 和 $m$ ，($1 \le n \le 100000$， $1 \le m \le 200000$) 表示遗迹数量和传送门数量。

接下来 $m$ 行，每行三个整数 $u, v, c$ ，($1 \le u, v \le n$, $1 \le c \le 1000000$) 表示遗迹 $u$ 和 $v$ 之间有一个协会 $c$ 的传送门。

保证样例中 $\sum n \leq 200000，\sum m \leq 400000$ 。

输出格式

每行输出一个整数，表示最小金币数。

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

3