There is an undirected weighted complete graph of vertices where is odd.
Let's define a cycle-array of size as an array of edges [e_1,e_2,\ldots ,e_k] that has the following properties:
is greater than .
For any from to , an edge e_i has exactly one common vertex with edge e_{i-1} and exactly one common vertex with edge e_{i+1} and these vertices are distinct (consider e_0 = e_k, e_{k+1} = e_1).
It is obvious that edges in a cycle-array form a cycle.
Let's define f(e_1, e_2) as a function that takes edges e_1 and e_2 as parameters and returns the maximum between the weights of e_1 and e_2.
Let's say that we have a cycle-array C = [e_1, e_2, \ldots, e_k]. Let's define the price of a cycle-array as the sum of f(e_i, e_{i+1}) for all from to (consider e_{k+1} = e_1).
Let's define a cycle-split of a graph as a set of non-intersecting cycle-arrays, such that the union of them contains all of the edges of the graph. Let's define the price of a cycle-split as the sum of prices of the arrays that belong to it.
There might be many possible cycle-splits of a graph. Given a graph, your task is to find the cycle-split with the minimum price and print the price of it.
The first line contains one integer (3 \le n\le 999, is odd) — the number of nodes in the graph.
Each of the following \frac{n \cdot (n-1)}{2} lines contain three space-separated integers , and (1 \le u,v \le n,u \neq v, 1 \le w \le 10^9), meaning that there is an edge between the nodes and that has weight .
Print one integer — the minimum possible price of a cycle-split of the graph.
Example 1
Example 2
Let's enumerate each edge in the same way as they appear in the input. I will use e_i to represent the edge that appears -th in the input.
The only possible cycle-split in the first sample 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.
The optimal cycle-split in the second sample is S = \{[e_3,e_8,e_9], [e_2,e_4,e_7,e_{10},e_5,e_1,e_6]\}. The price of [e_3,e_8,e_9] is equal to , the price of [e_2,e_4,e_7,e_{10},e_5,e_1,e_6] is equal to , thus the price of the split is equal to .