Bạn được cho một đồ thị vô hướng liên thông có trọng số. Định nghĩa chi phí của một đường đi độ dài \(k\) như sau:

• Gọi trọng số của tất cả các cạnh trên đường đi là \(w_1, \ldots, w_k\).

• Chi phí của đường đi là \((\min_{i=1}^{k} w_i) + (\max_{i=1}^{k} w_i)\), hay nói cách khác, là tổng của trọng số cạnh lớn nhất và nhỏ nhất.

Trong tất cả các đường đi từ đỉnh \(1\) đến \(n\), hãy báo cáo chi phí của đường đi có chi phí nhỏ nhất. Lưu ý rằng đường đi không nhất thiết phải đơn giản.

Input

Dòng đầu tiên chứa một số nguyên \(t\) \((1 \le t \le 10^4)\) — số lượng bộ test.

Dòng đầu tiên của mỗi test chứa hai số nguyên \(n\) và \(m\) \((2 \le n \le 2 \cdot 10^5,\ n - 1 \le m \le \min(2 \cdot 10^5,\ \frac{n(n - 1)}{2}))\).

\(m\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u\), \(v\) và \(w\) \((1 \le u, v \le n,\ 1 \le w \le 10^9)\) đại diện cho một cạnh giữa đỉnh \(u\) và đỉnh \(v\) với trọng số \(w\).
Đảm bảo rằng đồ thị không có vòng tự khép (self-loop), không có nhiều cạnh trùng nhau, và đồ thị là liên thông.

Ngoài ra đảm bảo rằng tổng tất cả \(n\) trong các test không vượt quá \(2 \cdot 10^5\) và tổng tất cả \(m\) trong các test cũng không vượt quá \(2 \cdot 10^5\).

Output

Với mỗi test, in ra một số nguyên duy nhất — chi phí nhỏ nhất của đường đi từ đỉnh 1 đến đỉnh n.

Sample Input

4
3 2
1 2 1
2 3 1
3 2
1 3 13
1 2 5
8 9
1 2 6
2 3 5
3 8 6
1 4 7
4 5 4
5 8 7
1 6 5
6 7 5
7 8 5
3 3
1 3 9
1 2 8
2 3 3

Sample Output

2
18
10
11