给定一个 $n$ 个顶点的无向加权完全图，其中 $n$ 为奇数。

定义一个大小为 $k$ 的循环数组（cycle-array）为一组边 $[e_1, e_2, \dots, e_k]$，满足以下性质： $k > 1$。 对于 $1$ 到 $k$ 的任意 $i$，边 $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, \dots, e_k]$，定义其代价（price）为所有 $f(e_i, e_{i+1})$ 的总和（其中 $1 \le i \le k$，且考虑 $e_{k+1} = e_1$）。

定义图的一个循环拆分（cycle-split）为一组互不相交的循环数组，使得它们的并集包含了图中所有的边。定义循环拆分的代价为其中所有循环数组代价的总和。

一个图可能存在多种循环拆分。给定一个图，你的任务是找到代价最小的循环拆分，并输出该代价。

输入格式

第一行包含一个整数 $n$ ($3 \le n \le 999, n$ 为奇数) —— 图中节点的数量。

接下来的 $\frac{n(n-1)}{2}$ 行，每行包含三个空格分隔的整数 $u, v$ 和 $w$ ($1 \le u, v \le n, u \neq v, 1 \le w \le 10^9$)，表示节点 $u$ 和 $v$ 之间存在一条权重为 $w$ 的边。

输出格式

输出一个整数 —— 该图循环拆分的最小可能代价。

样例

样例输入 1

3
1 2 1
2 3 1
3 1 1

样例输出 1

3

样例输入 2

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

样例输出 2

35

说明

我们将边按照它们在输入中出现的顺序进行编号。用 $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$。