E. Шаасс Великий
ограничение по времени на тест
3.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Великий Шаасс коронован как новый император Драхта. В империи есть n городов, их соединяет n - 1 двусторонних дорог. У каждой дороги есть определенная длина, каждая дорога соединяет пару городов. Каждую пару городов соединяет единственный простой путь.

Его величество великий Шаасс решил разрушить одну из дорог и построить другую дорогу той же длины между некоторой парой городов. Он должен построить дорогу так, чтобы было все еще возможно путешествовать из каждого города в любой другой по дорогам империи.

Вы как его советник должны помочь ему найти способ выполнить описанное действие. Вы должны найти такой способ, который минимизирует общую сумму попарных расстояний между городами. Вычислите минимальную сумму.

Входные данные

В первой строке содержится целое число n, обозначающее количество городов в империи, (2 ≤ n ≤ 5000). В следующих n - 1 строках содержится по три целых числа ai, bi и wi, обозначающие два города ai и bi, соединенные дорогой длины wi, (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ wi ≤ 106).

Выходные данные

В единственной строке выведите минимальную попарную сумму расстояний между городами.

Пожалуйста, не используйте спецификатор %lld для чтения и записи 64-битных чисел на С++. Рекоммендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
3
1 2 2
1 3 4
Выходные данные
12
Входные данные
6
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
Выходные данные
29
Входные данные
6
1 3 1
2 3 1
3 4 100
4 5 2
4 6 1
Выходные данные
825