Description

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

A cycle edge group of size $k$ is an array of edges $[e_1, e_2, \dots, e_k]$ that satisfies:

• $k$ is greater than $1$.
• For any integer $i$ in $[1, k]$, the edge $e_i$ shares exactly one common endpoint with each of $e_{i-1}$ and $e_{i+1}$ (where $e_0 = e_k$ and $e_{k+1} = e_1$).

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

Define a function $f(e_1, e_2)$ for two edges $e_1, e_2$ as the larger of their edge weights.

Define the value of a cycle edge group $C = [e_1, e_2, \dots, e_k]$ as the sum of $f(e_i, e_{i+1})$ over all integers $i$ in $[1, k]$ (where $e_{k+1} = e_1$).

Define a cycle decomposition of a graph as a set of pairwise disjoint cycle edge groups whose union contains all edges of the graph. Define the value of a cycle decomposition as the sum of the values of all cycle edge groups in it.

A graph may have multiple cycle decompositions. Given a graph, your task is to find the cycle decomposition 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)$, indicating that there is an edge of weight $w$ between vertex $u$ and vertex $v$.

Output Format

Output one integer, representing the value of the minimum-value cycle decomposition of the given graph.

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

Hint

In the following sample explanations, edges are numbered in input order, and $e_i$ denotes the $i$-th edge in the input order.

In the first sample, the only cycle decomposition is $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$.

In the second sample, an optimal cycle decomposition 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$, so the value of the cycle decomposition is $35$.

Translated by ChatGPT 5