Имеется неориентированный взвешенный полный граф из n вершин, где n нечетно.

Определим циклический массив размером k как массив ребер [e1, e2, ..., ek], обладающий следующими свойствами:

• k больше 1.
• Для любого i от 1 до k ребро ei имеет ровно одну общую вершину с ребром ei-1 и ровно одну общую вершину с ребром ei+1, причем эти вершины различны (считайте e0 = ek, ek+1 = e1).

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

Определим f(e1, e2) как функцию, которая принимает ребра e1 и e2 в качестве параметров и возвращает максимум между весами e1 и e2.

Пусть у нас имеется циклический массив C = [e1, e2, ..., ek]. Определим цену циклического массив как сумму f(ei, ei+1) для всех i от 1 до k (ek+1 = e1).

Определим циклическое разбиение графа как набор непересекающихся циклических массивов, объединение которых содержит все ребра графа. Определим цену циклического разбиения как сумму цен принадлежащих ему массивов.

Существует много возможных циклических разбиений графа. Ваша задача - найти циклическое разбиение с минимальной ценой и вывести эту цену.

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

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

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

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

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

Пояснение

Давайте пронумеруем ребра в таком же порядке, как они появляются во входных данных. Обозначим через ei ребро, которое появляется i-ым во входных данных.

Единственным возможным циклическим разбиением графа в первом примере является S = {[e1, e2, e3]}: f(e1, e2) + f(e2, e3) + f(e3, e1) = 1 + 1 + 1 = 3.

Оптимальное циклическое разбиение графа во втором примере: S = {[e3, e8, e9], [e2, e4, e7, e10, e5, e1, e6]}. Цена [e3, e8, e9] равна 12, цена [e2, e4, e7, e10, e5, e1, e6] равно 23, поэтому цена разбиения равна 35.