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.

Để 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,...,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\), \(\ldots\), \(x_k\) tới \(v\). Ta kí hiệu độ dài của đường đi từ \(u\) tới \(v\) là \(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à \(distance(y,S)\). Giá trị của cách chọn này chính bằng \(value(u,v) \times distance(y,S)\).

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

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

Input

• Dòng thứ nhất chứa một số nguyên dương \(n\) \((1 \leq n \leq 3 \times 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 \leq u, v \leq n, 1 \leq w \leq 10^{3})\) thể hiện có đường đi trực tiếp giữa phòng \(u\) và \(v\), độ dài của đường đó là \(w\).

Output

• Gồm một số nguyên duy nhất là độ quan trọng lớn nhất.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n \leq 100\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 3000\).
• Subtask \(3\) (\(30\%\) số điểm): Mỗi phòng của mê cung có tối đa \(3\) đường nối trực tiếp đến.
• Subtask \(4\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

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

15