GSFOS có dự định thám hiểm một mê cung, bằng cách thần kì nào đó mà anh ấy đã lấy được bản thiết kế của mê cung này. Mê cung gồm ~n~ phòng nối liền thông với nhau bằng ~n - 1~ con đường trực tiếp, con đường trực tiếp thứ ~i~ (~1 \le i < n~) nối hai phòng ~u_i~ và ~v_i~ với nhau, có độ dài là ~w_i~. Cửa ra/vào mê cung được đặt ở những phòng chỉ có một con đường nối đến trực tiếp (nút lá).

Để thuận tiện cho việc thám hiểm mê cung, GSFOS cần chọn ra một đường đi trên mê cung nối hai đỉnh ~u~ đến ~v~ bất kì sao cho gọi tập đỉnh của đường đi này lần lượt là ~S = \{u, x_1, x_2, \ldots, x_k, v\}~ thì ta luôn có cạnh trực tiếp nối từ ~u~ tới ~x_1~, ~x_1~ tới ~x_2~, ..., ~x_k~ tới ~v~. Ta kí hiệu độ dài của đường đi từ ~u~ tới ~v~ là ~\mathrm{value}(u, v)~. Tiếp theo, GSFOS cần chọn ra một đỉnh không thuộc tập đỉnh ~S~ đã chọn trước đó, coi đỉnh tìm được là đỉnh ~y~ thì ta kí hiệu độ dài của đường đi từ đỉnh ~y~ tới một trong các đỉnh thuộc tập đỉnh ~S~ sao cho giá trị này là nhỏ nhất có thể là ~\mathrm{distance}(y, S)~. Giá trị của cách chọn này chính bằng ~\mathrm{value}(u, v) \cdot \mathrm{distance}(y, S)~.

Lưu ý: nếu không chọn được đỉnh ~y~ thoả mãn thì ~\mathrm{distance}(y, S) = 0~, nếu không chọn được hai đỉnh ~u~, ~v~ thoả mãn để làm đường đi thì ~\mathrm{value}(u, v) = 0~.

GSFOS muốn tối đa hoá giá trị ~\mathrm{value}(u, v) \cdot \mathrm{distance}(y, S)~. Hãy giúp GSFOS tính giá trị lớn nhất của bài toán.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên dương ~n~ (~1 \le n \le 3 \cdot 10^5~) là số lượng phòng trong mê cung.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa ~3~ số nguyên ~u~, ~v~ và ~w~ (~1 \le u, v \le n~, ~1 \le w \le 10^9~) thể hiện có đường đi trực tiếp giữa phòng ~u~ và ~v~, độ dài của đường đó là ~w~.

Kết quả

• Một số nguyên duy nhất là độ quan trọng lớn nhất (kết quả bài toán).

Ví dụ

Đầu vào:

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

Đầu ra:

15

Giải thích: Một trong những đường đi cho ra độ quan trọng lớn nhất là đường đi từ phòng ~2~ đến phòng ~5~, đường này có độ dài là ~5~, phòng có khoảng cách lớn nhất với đường đi này là phòng ~4~, có khoảng cách với đường quan trọng kia là ~3~, lúc này độ quan trọng của đường đi sẽ là ~5 \times 3 = 15~.

Giới hạn

• ~1 \le n \le 3 \cdot 10^5~
• ~1 \le w \le 10^9~

Điểm của một subtask chỉ được tính khi tất cả các test thuộc subtask đó đều đúng. Lưu ý rằng kết quả có thể vượt quá phạm vi kiểu số nguyên 32 bit.