Trung tâm Công nghệ Thông tin vừa hoàn thành mạng cáp quang nối ~n~ toà nhà của Đại học Công nghiệp Hà Nội, các toà nhà được đánh số từ ~1~ đến ~n~. Mạng gồm đúng ~n - 1~ tuyến cáp hai chiều; tuyến thứ ~j~ nối trực tiếp hai toà nhà ~u_j~ và ~v_j~, có độ dài ~w_j~. Giữa hai toà nhà bất kỳ luôn có đúng một đường truyền (đường đi qua các tuyến cáp, không đi lại tuyến nào hai lần).

Độ trễ giữa hai toà nhà bằng tổng độ dài các tuyến cáp trên đường truyền duy nhất giữa chúng. Kỹ sư của Trung tâm cần biết độ trễ lớn nhất có thể xảy ra trong mạng.

Yêu cầu

Hãy tìm độ trễ lớn nhất giữa hai toà nhà trong mạng. Nếu ~n = 1~ thì kết quả bằng ~0~.

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên ~n~;
• ~n - 1~ dòng tiếp theo, dòng thứ ~j~ chứa ba số nguyên ~u_j~, ~v_j~ và ~w_j~.

Kết quả ra

Ghi ra một số nguyên duy nhất là độ trễ lớn nhất tìm được.

Ràng buộc

~1 \le n \le 2 \cdot 10^5~; ~1 \le u_j, v_j \le n~; ~u_j \ne v_j~; ~1 \le w_j \le 10^9~; dữ liệu đảm bảo giữa hai toà nhà bất kỳ có đúng một đường truyền.

• Subtask 1 (15% số điểm – test 01–04): ~n \le 100~ và ~w_j \le 10^6~;
• Subtask 2 (20% số điểm – test 05–08): ~n \le 3000~;
• Subtask 3 (20% số điểm – test 09–12): mỗi toà nhà nối trực tiếp với không quá hai toà nhà khác;
• Subtask 4 (45% số điểm – test 13–20): không có ràng buộc bổ sung.

Lưu ý: kết quả có thể vượt quá phạm vi kiểu số nguyên 32 bit.

Ví dụ

Dữ liệu vào mẫu 1

6
1 2 2
2 3 2
3 4 2
1 5 10
6 1 7

Kết quả ra mẫu 1

17

Giải thích

Độ trễ lớn nhất là giữa toà nhà ~5~ và toà nhà ~6~: đường truyền ~5 - 1 - 6~ có tổng độ dài ~10 + 7 = 17~. Một đường truyền qua nhiều tuyến cáp nhất, chẳng hạn ~5 - 1 - 2 - 3 - 4~, chỉ có tổng độ dài ~16~.