Reorganization of Highway Network

The highway network in the country of Zuia consists of cities (points) and the roads that connect them. This highway network has been constructed to meet the following conditions:

• There are $N$ cities (points) assigned the numbers 1 to $N$.
• The roads are one-way, and there are only two roads at most that directly connect one point to another (and when there are two, they are opposite of each other).
• From any point, you can always get to all the other points.

Maintaining a highway network costs money for each road. To avoid financial difficulties, the country of Zuia has decided to discontinue some roads and has appointed you as the person in charge. You have to reorganize the entire highway network so that the cost of maintaining it is minimized, without changing the conditions above.

Write a program which reads the number of points and information about the roads and finds the minimum maintenance cost of the entire highway network after the reorganization.

Input

The input is given in the following form.

$N$ $M$
$u_1$ $v_1$ $c_1$
$u_2$ $v_2$ $c_2$
:
$u_M$ $v_M$ $c_M$

In the first line, the number of points $N$ ($2 \leq N \leq 13$) and the number of roads $M$ ($N \leq M \leq N \times (N-1)$) are given. In the following $M$ lines, the starting point $u_i$ and the ending point $v_i$ of the $i$-th road ($1 \leq u_i \ne v_i \leq N$) and the maintenance cost $c_i$ ($1 \leq c_i \leq 10,000$) are given.

Output

Output the minimum value of the maintenance cost of the entire highway network after the reorganization in a line.  

Sample Input and Output

Sample Input 1

3 4
1 2 2
2 3 3
1 3 1
3 1 1

Sample Output 1

6

Sample Input 2

5 8
1 2 7
1 5 2
2 1 8
2 3 3
3 4 5
4 5 8
5 1 5
5 2 1

Sample Output 2

24

 

---