题目描述

有一个 $n$ 个点的无向有边权的完全图，其中 $n$ 是奇数。

定义一个大小为 $k$ 的环边组为一个边构成的数组 $[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$）。

显然一个环边组中的边构成了图上的一个环。

定义一个参数为两条边 $e_1, e_2$ 的函数 $f(e_1, e_2)$，其函数值为两条边中边权的较大值。

定义一个环边组 $C=[e_1, e_2, \dots, e_k]$ 的价值为对于任意 $[1, k]$ 中的整数 $i$，$f(e_i, e_{i+1})$ 的值之和（规定 $e_{k+1}=e_1$）。

定义一个图的环分割为一组无交集的环边组，且这些环边组的并包含了图上所有的边。定义一个图的环分割的价值为其中所有环边组的价值之和。

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

输入格式

第一行包含一个整数 $n \ (3 \leq n \leq 999, n \bmod 2 = 1)$，代表图的点数。

接下来的 $\frac{n\cdot (n-1)}{2}$ 行每行包含三个整数 $u, v$ 和 $w \ (1 \leq u, v \leq n, u \neq v, 1 \leq w \leq 10^9)$，代表点 $u$ 和点 $v$ 间有一条边权为 $w$ 的边。

输出格式

输出一个整数，代表给定图的最小价值环分割的价值。

3
1 2 1
2 3 1
3 1 1

3

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

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$。