Граф і цикли

Маємо неорієнтований зважений повний граф з n вершинами, де n є непарним числом.

Циклічний масив розміру k визначається як масив ребер [e[1], e[2], ..., e[k]], що задовольняє наступні умови:

• k більше 1.

• Для кожного i від 1 до k ребро e[i] має рівно одну спільну вершину з ребром e[i-1] і одну спільну вершину з ребром e[i+1], причому ці вершини різні (вважайте e[0] = e[k], e[k+1] = e[1]).

Очевидно, що ребра в циклічному масиві утворюють цикл.

Функція f(e[1], e[2]) визначається як максимум між вагами ребер e[1] і e[2].

Нехай у нас є циклічний масив C = [e[1], e[2], ..., e[k]]. Ціна циклічного масиву визначається як сума f(e[i], e[i+1]) для всіх i від 1 до k (e[k+1] = e[1]).

Циклічне розбиття графа - це набір неперетинних циклічних масивів, об'єднання яких містить усі ребра графа. Ціна циклічного розбиття - це сума цін його масивів.

Існує багато можливих циклічних розбиттів графа. Ваше завдання - знайти циклічне розбиття з мінімальною ціною і вивести цю ціну.

Вхідні дані

Перший рядок містить одне ціле число n (3 ≤ n ≤ 999, n непарне) - кількість вершин у графі.

Кожен з наступних n * (n - 1) / 2 рядків містить три цілі числа: u, v і w (1 ≤ u, v ≤ n, u ≠ v, 1 ≤ w ≤ 10^9), що означають, що між вершинами u і v є ребро з вагою w.

Вихідні дані

Виведіть одне ціле число - мінімально можливу ціну циклічного розбиття графа.

Приклади

Примітка

Пронумеруємо ребра в порядку їх появи у вхідних даних. Позначимо через e[i] ребро, яке з'являється i-им у вхідних даних.

Єдиним можливим циклічним розбиттям графа в першому прикладі є S = {[e[1], e[2], e[3]]}: f(e[1], e[2]) + f(e[2], e[3]) + f(e[3], e[1]) = 1 + 1 + 1 = 3.

Оптимальне циклічне розбиття графа у другому прикладі: S = {[e[3], e[8], e[9]], [e[2], e[4], e[7], e[10], e[5], e[1], e[6]]}. Ціна [e[3], e[8], e[9]] дорівнює 12, ціна [e[2], e[4], e[7], e[10], e[5], e[1], e[6]] дорівнює 23, тому загальна ціна розбиття дорівнює 35.