💫Đề bài: An đang gặp một bài toán rất nổi tiếng trên mạng. An không biết cách giải thế nào đành nhớ các coder. Các coder thông minh hãy giải bài toán này nhé!

🧩Mission: Hãy giải bài toán nổi tiếng trên với n là một số nguyên (Giới hạn: n < 10^15)
📥Input: Một số nguyên là n (n \(1015\))
📤Output: Kết quả của bài toán.

🧪Ví dụ:

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

Silver Wolf đưa cho bạn một mảng \(a\) có độ dài \(n\) và \(q\) truy vấn. Trong mỗi truy vấn, cô ấy thay thế một phần tử trong \(a\). Sau mỗi truy vấn, cô ấy yêu cầu bạn xuất ra số nguyên lớn nhất \(k\) sao cho tồn tại một số nguyên \(x\) sao cho \(x\) là \(k\)-majority của một dãy con bất kỳ* của \(a\).

Một số nguyên \(y\) được gọi là \(k\)-majority của dãy \(b\) nếu \(y\) xuất hiện ít nhất \(\left\lfloor \frac{|b| + 1}{2} \right\rfloor + k\) lần trong \(b\), trong đó \(|b|\) là độ dài của \(b\). Lưu ý rằng \(b\) không nhất thiết phải có \(k\)-majority.

• Một dãy \(b\) là dãy con của dãy \(a\) nếu \(b\) có thể thu được từ \(a\) bằng cách xóa một số (có thể là không, có thể là tất cả) phần tử từ đầu và một số (có thể là không, có thể là tất cả) phần tử từ cuối.

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à \(q\) (\(1 \le n, q \le 3 \cdot 10^5\)) — độ dài của mảng \(a\) và số truy vấn.

Dòng tiếp theo chứa \(n\) số nguyên cách nhau bởi dấu cách \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le n\)).

\(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(i\) và \(x\), biểu thị truy vấn thay thế \(a_i\) bằng \(x\) (\(1 \le i, x \le n\)).

Đảm bảo rằng tổng tất cả các \(n\) và tổng tất cả các \(q\) qua mọi test không vượt quá \(3 \cdot 10^5\).

Output

Với mỗi test, xuất ra kết quả của tất cả các truy vấn trên một dòng, cách nhau bởi dấu cách.

Sample Input 1

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

1 1 2 1 0 
2 2 3 2 1 1 1 2