Pháo đài

GSFOS chuẩn bị thám hiểm một pháo đài cổ. Pháo đài có \(n\) phòng, nối liên thông với nhau bằng \(n-1\) đường hầm. Đường hầm thứ \(i\) nối hai phòng \(u_i\) và \(v_i\) với nhau và có độ dài \(w_i\).

Để lên kế hoạch thám hiểm, GSFOS cần chọn một đường đi nối hai phòng \(u\) và \(v\) bất kỳ. Gọi tập các đỉnh trên đường này là
\(S=\{u,x_1,x_2,\dots,x_k,v\}\),
theo thứ tự sao cho có cạnh nối lần lượt \(u\text{--}x_1\text{--}x_2\text{--}\dots\text{--}x_k\text{--}v\). Độ dài của đường đi từ \(u\) tới \(v\) được ký hiệu là \(\operatorname{value}(u,v)\).

Sau khi chọn đường \(S\), GSFOS chọn một phòng \(y\) không thuộc \(S\). Định nghĩa

trong đó \(\operatorname{dist}(y,z)\) là khoảng cách giữa hai phòng \(y\) và \(z\). Nếu không tồn tại phòng \(y\) phù hợp (tức mọi phòng đều thuộc \(S\)) thì ta lấy \(\operatorname{distance}(y,S)=0\). Nếu không thể chọn được hai phòng \(u,v\) để tạo thành đường đi thì \(\operatorname{value}(u,v)=0\).

Giá trị của cách chọn là

Hãy tính giá trị lớn nhất có thể đạt được khi tối ưu hóa cả đường \(S\) (tức chọn \(u,v\)) và phòng \(y\).

Input

• Dòng đầu chứa một số nguyên dương \(n\) (\(1\le n \le 3\cdot 10^5\)) --- số phòng trong pháo đài.
• \(n-1\) dòng tiếp theo, mỗi dòng gồm ba số nguyên \(u, v, w\) (\(1\le u,v\le n\), \(1\le w\le 10^3\)) --- có một đường hầm giữa phòng \(u\) và \(v\) với độ dài \(w\).

Output

• In ra một số nguyên duy nhất --- giá trị lớn nhất của \(\operatorname{value}(u,v)\times \operatorname{distance}(y,S)\) có thể đạt được.

Example

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

15

Scoring

• Subtask 1 (15%): \(n \le 100\).
• Subtask 2 (20%): \(n \le 3000\).
• Subtask 3 (30%): Mỗi phòng có tối đa \(3\) đường hầm kề.
• Subtask 4 (35%): Không có ràng buộc gì thêm.