Problem Description

There is an undirected complete graph with edge weights, consisting of $n$ vertices, where $n$ is an odd number.

A cycle edge group of size $k$ is defined as an array of edges $[e_1, e_2, \dots, e_k]$ with the following properties:
- $k$ is greater than 1.
- For any integer $i$ in the range $[1, k]$, edge $e_i$ shares exactly one endpoint with both $e_{i-1}$ and $e_{i+1}$ (with the convention that $e_0 = e_k$ and $e_{k+1} = e_1$).

Clearly, the edges in a cycle edge group form a cycle in the graph.

A function $f(e_1, e_2)$ is defined for two edges $e_1$ and $e_2$, where the value of the function is the larger of the two edge weights.

The value of a cycle edge group $C = [e_1, e_2, \dots, e_k]$ is defined as the sum of $f(e_i, e_{i+1})$ for all integers $i$ in the range $[1, k]$ (with the convention that $e_{k+1} = e_1$).

A cycle partition of a graph is defined as a set of disjoint cycle edge groups whose union includes all the edges of the graph. The value of a cycle partition of a graph is the sum of the values of all its cycle edge groups.

A graph may have multiple cycle partitions. Given a graph, your task is to find the cycle partition with the minimum value and output this minimum value.

Input Format

The first line contains an integer $n \ (3 \leq n \leq 999, n \bmod 2 = 1)$, representing the number of vertices in the graph.

The next $\frac{n \cdot (n-1)}{2}$ lines each contain three integers $u, v$, and $w \ (1 \leq u, v \leq n, u \neq v, 1 \leq w \leq 10^9)$, representing an edge with weight $w$ between vertices $u$ and $v$.

Output Format

Output a single integer, representing the minimum value of the cycle partition of the given graph.

Sample Input and Output

Sample Input #1

3
1 2 1
2 3 1
3 1 1

Sample Output #1

3

Sample Input #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

Sample Output #2

35

Notes

In the sample explanations below, edges are numbered in the order of input, with $e_i$ representing the $i$-th edge in the input order.

In the first sample, the only cycle partition is $S = \{ [e_1, e_2, e_3] \}$. The value of $f(e_1, e_2) + f(e_2, e_3) + f(e_3, e_1) = 1 + 1 + 1 = 3$.

In the second sample, the optimal cycle partition is $S = \{ [e_3, e_8, e_9], [e_2, e_4, e_7, e_{10}, e_5, e_1, e_6] \}$. The value of the cycle edge group $[e_3, e_8, e_9]$ is $12$, and the value of $[e_2, e_4, e_7, e_{10}, e_5, e_1, e_6]$ is $23$, thus the value of the cycle partition is $35$.

见题面 Input 部分

见题面 Output 部分