某連鎖商店有 N 個分店，總公司打算建構一個網路將所有據點的電腦系統連接起來。經過顧問公司所做的調查，某些分店之間可以架設線路，但有些不能。架設線路也各自需要不同的成本。該公司現在對外招標連線的設計，由於該公司還有其他的考量，所以希望每一個投標廠商必須提出兩個不同的網路連線設計。根據該公司公告的可能線路成本資料，你的工作是計算出最佳以及次佳網路的建構成本之差值。

N 個分店的編號為 0~N–1，要將這些分店連接成一個網路，至少需要 N–1 條連線。把每一個分店看成一個點，點與點之間有一些具某些成本的邊，邊代表可以選擇的連線成本，一個網路設計就是要選出某些邊將所有的點連成一個連通的區塊使得任兩點之間皆可直接或間接相連，而其成本就是所選擇的邊的成本總和，在這個問題中，你要求的是最小成本和次小成本的網路設計。所謂次小成本，是指成本大於最小成本的解中，成本最小的。

以圖一為例，(a)是輸入資料，包含四個點和六個可能的連線；(b)是將四個點連成連通網路的最小成本，其成本為 1+2+4=7；(c)是次小成本，其成本為 9；(d)的成本是10，因此他不是本題所求的答案。請留意，如圖一(a)，本題中兩點之間可能有超過一個邊，次小成本有可能使用這些邊。在此例中，最小與次小的成本差值就是 9–7=2。 

第一行有一個整數 T (T<=8)，表示有 T 個測試資料。

每個測試資料的第一行有兩正整數 N (N<=2000)和 M (M<=15000)，代表共有 N 個分店需要被連接以及有M 個可能的連線架設方式，分店的編號是 0~N–1。接下來的 M 行每行有三個整數字表示一個可能的連線架設方式，前兩個數字是連接的兩個分店，第三個數字是這個連線的成本：一個不超過 500,000 的正整數。連線的成本皆不相同，所求答案不會超過 2³¹。 

輸入1:
1
4 6
0 1 1
2 0 2
3 1 8
3 0 7
1 2 6
2 3 10

輸入2:
2
3 4
0 1 3
2 1 4
0 2 6
1 2 5
5 5
0 1 1
1 2 3
3 2 4
3 4 8
0 4 10

輸入3:
1
6 7
0 1 1
0 2 2
1 3 3
1 4 4
2 5 5
5 3 6
1 3 7

輸出1:
1

輸出2:
1
2

輸出3:
1

註：原題最高難度測資為 N<=20000、M<=130000，本系統降低難度取第二難度之測資範圍。