Vũ trụ có tất cả ~n~ vì sao được đánh số từ ~1~ đến ~n~ và ~n-1~ cây cầu Ô Thước, cầu thứ ~i~ nối hai vì sao ~u_i~ và ~v_i~ với nhau, có số bậc thang là ~w_i~. Dữ liệu đảm bảo giữa hai vì sao bất kỳ luôn có con đường hai chiều đi đến được với nhau trực tiếp hoặc thông qua một số vì sao khác.

Không hiểu nguyên nhân gì mà vợ chồng Ngưu Lang và Chức Nữ tuyệt tình đến mức phải chọn hai vì sao xa nhau nhất để mỗi người sinh sống tại một trong hai vì sao đó.

Yêu cầu: Hãy lập trình cho biết độ dài đường đi (tổng số bậc thang) giữa hai vì sao mà Ngưu Lang và Chức Nữ đang sinh sống.

Input

• Dòng đầu tiên chứa một số nguyên dương ~n~ (~n \le 2 \cdot 10^5~);

• Dòng thứ ~i~ trong ~n-1~ dòng sau, mỗi dòng gồm ba số nguyên dương ~u_i, v_i, w_i~ ghi cách nhau bởi một khoảng trống (~u_i, v_i \le n; w_i \le 10^9; 1 \le i < n~).

Output

Ghi ra một số nguyên là độ dài đường đi tìm được.

Scoring

Sample Input 1

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

Sample Output 1

9

Notes

Hai vì sao mà Ngưu Lang và Chức Nữ sinh sống có số thứ tự là: ~3~ và ~4~.