問題文

N 個の部屋と M 本の通路からなる建物があります。 部屋には 1 から N までの番号が付けられており、i 番目の通路は部屋 A_i と部屋 B_i を双方向に結び、通るのに C_i 分かかります。 どの部屋同士も、通路をいくつか経由して行き来することが可能です。

現在、soryuusi 君は部屋 1 にいます。 建物から脱出するためには、部屋 N の出口から出る必要がありますが、そのためには以下のミッションを順番に達成しなければなりません。

1. 部屋 x へ行き、キューブを回収する。
2. 部屋 y へ行き、スイッチにキューブを置いて作動させる。
3. 部屋 N へ向かい、出口から脱出する。

なお、ミッションの順番を無視して対象の部屋に訪れてもかまいませんが、現在の進行段階に合致しないミッションをその場で進めることはできません。例えば、部屋 x を訪れる前に部屋 y を訪れてもかまいませんが、キューブを回収していないため、そこでスイッチを作動させることはできません。

最初、赤と青のポータルはいずれも存在しません。 soryuusi 君は、以下のいずれかの行動を任意の順序・回数で行うことができます。

• 今いる部屋と通路で繋がっている隣の部屋へ歩いて移動する。
• 今いる部屋に「赤」または「青」のポータルを作る。すでに同色のポータルが存在していた場合、古いポータルは消滅し、現在の部屋に新しく作られる。
• 今いる部屋にポータルがあり、別の部屋にもう片方の色のポータルがある場合、そのポータルを通って一瞬でもう一方の部屋へ移動する。このとき、各ポータルは元の位置に残る。

soryuusi 君がミッションをすべて達成し、出口から脱出するまでに必要な最小の時間を求めてください。 ただし、ポータルの作成、ポータル間の移動、キューブの回収やスイッチの作動など、通路を歩いて移動する以外の行動にかかる時間はすべて無視できるものとします。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• 1 \leq T \leq 5 \times 10^4
• 4 \leq N \leq 2 \times 10^5
• N-1 \leq M \leq 2 \times 10^5
• 1 \leq A_i < B_i \leq N \ (1 \leq i \leq M)
• (A_i, B_i) \neq (A_j, B_j) \ (i \neq j)
• 1 \leq C_i \leq 10^9 \ (1 \leq i \leq M)
• どの部屋の間もいくつかの通路を経由して行き来することができる
• 1 < x < y < N
• すべてのテストケースについての N の総和は 2 \times 10^5 以下
• すべてのテストケースについての M の総和は 2 \times 10^5 以下
• 入力される数値はすべて整数

入力例 1

3
5 5 2 4
1 2 5
1 3 2
1 4 4
3 4 3
3 5 1
6 8 3 5
5 6 33
4 5 65
3 4 45
1 6 34
1 4 38
1 5 72
3 6 77
2 4 42
13 19 4 8
3 13 840297721
11 12 168431768
3 5 130461050
6 10 36799323
1 11 819050961
11 13 309758082
8 11 544077695
1 7 665727915
6 9 68458882
3 7 540529111
1 12 934170727
6 8 657150845
7 12 767322822
7 9 251057149
4 6 873778475
6 7 772247050
5 6 442838729
2 5 30650990
2 9 457409811

出力例 1

11
144
3370009043

1 つめのテストケースについて、soryuusi 君は以下のように行動することで、11 分で出口から脱出できます。

• 部屋 1 に赤のポータルを作る。
• 部屋 1 から部屋 2 に 5 分かけて移動する。
• 部屋 2 でキューブを回収する。
• 部屋 2 に青のポータルを作る。
• ポータルを通って部屋 2 から部屋 1 に移動する。
• 部屋 1 から部屋 3 に 2 分かけて移動する。
• 部屋 3 に青のポータルを作る。部屋 2 の青のポータルは消滅する。
• 部屋 3 から部屋 4 に 3 分かけて移動する。
• 部屋 4 でスイッチにキューブを置いて作動させる。
• 部屋 4 に赤のポータルを作る。部屋 1 の赤のポータルは消滅する。
• ポータルを通って部屋 4 から部屋 3 に移動する。
• 部屋 3 から部屋 5 に 1 分かけて移動する。

11 分より短い時間で出口から脱出することはできないので、11 を出力します。