Vào năm 2118, đế chế UP trở thành đế chế vĩ đại nhất thế giới. UP gồm ~N~ thành phố được kết nối bởi ~N - 1~ con đường ~2~ chiều và ~2~ thành phố bất kì được nối bởi đúng một con đường. Vị vua Purple đang muốn xóa ~1~ con đường đang có và xây ~1~ con đường mới có cùng độ dài sao cho vẫn đảm bảo từ thành phố bất kì có thể đi đến mọi thành phố khác. Bạn hãy giúp ngài Purple tìm cách thay đổi sao cho tổng khoảng cách từ ~2~ thành phố bất kì là nhỏ nhất. Nói cách khác, gọi ~dist(u,v)~ là độ dài đường đi ngắn nhất từ ~u~ tới ~v~, Purple muốn cực tiểu giá trị ~\displaystyle\sum_{u=1}^{n-1}\displaystyle\sum_{v=u+1}^{n} dist(u,v)~ với mọi cách thay đổi đường.

Input

• Dòng đầu tiên gồm số tự nhiên ~N~ ~(N \leq 5*10^3)~;
• ~N - 1~ dòng tiếp theo, mỗi dòng gồm ~3~ số ~u, v, c~ biểu diễn một con đường ~(u, v \leq N; c \leq 10^9)~.

Output

Gồm 1 dòng duy nhất là giá trị nhỏ nhất có thể có với mọi cách thay đổi đường.

Sample Input

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

Sample Output

290

Note

Ta sẽ bỏ con đường thứ hai ~(3, 4, 10)~ thay bằng con đường ~(2, 5, 10)~.

Subtask

• 20% số test có ~N \leq 20~;
• 30% số test có ~N \leq 100~;
• 20% số test có ~N~ thành phố tạo thành đường thẳng và các con đường chỉ có độ dài ~1~.
• 30% số test còn lại không có giới hạn thêm.