Problem Statement

The Pokemon craze is on! As a salesman, Len the Hamster is trying to build a floor display to showcase and sell Pokemon soft toys.

There's just one problem before his shop can open: he's out of stock, so he needs to visit every shop in town to pick up the soft toys.

Because businesses are all about minimising costs, Len wants to make the shortest possible trip.

The town can be modelled as a simple complete graph, consisting of V shops and V*(V-1)/2 roads. Each shop is labelled 0 to V-1. Roads are bidirectional edges of length Wi connecting shops Ai and Bi.

Len starts at vertex 0, and wants to visit every shop exactly once to pick up all the toys, before returning to his shop at vertex 0.

Help Len calculate the distance of the shortest route!

Input

You are to input from standard input.

The first line of input consists of 1 integer, V, the number of shops (including Len's shop).

V*(V-1)/2 lines will follow. Each line describes a bidirectional road.

The following V*(V-1)/2 lines of input will consist of 3 integers Ai Bi Wi. It costs Wi dollars to travel from shop Ai to shop Bi.

Output

Print an integer denoting the minimum cost.

Limits

For all subtasks:

Subtask 1 (40%): 1 < V ≤ 12

Subtask 2 (15%): 1 < V ≤ 1000

Subtask 3 (45%): 1 < V ≤ 100,000

Subtask 4 (0%): As per sample testcases.

Sample Input 1

2
0 1 4

Sample Output 1

8

Sample Input 2

4
0 1 5
0 2 1
0 3 1000
1 2 10
1 3 1
2 3 3

Sample Output 2

10

Explanation for Sample Input 2: The optimal route is 0->1->3->2->0. So the total cost is 5+1+3+1=10.

Sample Input 3

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

Sample Output 3

0

Explanation for Sample Input 3: There's no free lunch in this world. But hey, at least travelling is free!

Footnote

Len finds a tag on the floor display. It reads: "Anagram".

It is guaranteed that a solution which solves subtask 4 (sample) will solve subtasks 1-3 too.