Chiến thắng vĩnh cửu

Có $N$ thành phố được đánh số từ $1$ đến $N$, nối với nhau bởi $N-1$ con đường hai chiều. Giữa hai thành phố bất kỳ luôn tồn tại đúng một đường đi, tức là mạng lưới tạo thành một cây. Mỗi con đường có một độ dài cho trước.

Một người đang ở thành phố $1$ và muốn đi thăm tất cả các thành phố còn lại, mỗi thành phố ít nhất một lần. Người đó có thể kết thúc hành trình tại một thành phố bất kỳ (không bắt buộc quay về thành phố $1$).

Hãy tìm tổng quãng đường nhỏ nhất mà người đó phải di chuyển.

Dữ liệu vào

• Dòng đầu chứa số nguyên $N$ — số thành phố.
• $N-1$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $x_i$, $y_i$, $w_i$ — con đường nối hai thành phố $x_i$ và $y_i$ có độ dài $w_i$.

Dữ liệu ra

• Một số nguyên duy nhất — tổng quãng đường nhỏ nhất.

Ràng buộc

• $1\le N\le {10}^5$
• $1\le x_i,y_i\le N$
• $0\le w_i\le 2\times {10}^4$

Ví dụ