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

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

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

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

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

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

Input

第一行输入一个整数 $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\le 200000$，$\sum m\le 400000$。

Output

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

Sample

Input

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

Output

3