Cho đồ thị vô hướng liên thông có ~n~ đỉnh và ~n−1~ cạnh. Hãy tìm một cặp đỉnh ~u,v~ sao cho đường đi từ ~u~ tới ~v~ có tổng trọng số lớn nhất.

Dữ liệu vào:

• Dòng đầu tiên là số nguyên ~t~ cho biết số lượng testcase
• ~t~ nhóm dòng tiếp theo, mỗi nhóm dòng cho biết thông tin về một testcase: Dòng đầu tiên ghi số nguyên dương ~n~ cho biết số đỉnh của đồ thị ~n−1~ dòng tiếp theo, mỗi dòng ghi ba số nguyên ~u,v,c~ cho biết cạnh ~u,v~ của đồ thị có trọng số ~c~.

Giới hạn:

• ~1 ≤ t ≤ 10~
• ~2 ≤ n ≤ 50000~
• ~0 ≤ c ≤ 20000~

Kết quả: Gồm ~t~ dòng, mỗi dòng ghi kết quả của một testcase tương ứng với thứ tự trong input

Ví dụ:

Input 1:

1
6
1 2 3
2 3 4
2 6 2
6 4 6
6 5 5

Output 1:

12