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 đơn từ ~u~ đến ~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~.

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

Ràng buộc

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

Ví dụ:

Input 1

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

Output 1

12