Note

Problem Statement

The network of Yukicoder Express Inc. has $N$ stations and $M$ tracks, each bidirectionally connecting two stations.
The $i$-th track connects station $a_i$ and station $b_i$, and its length is $c_i$.

One day, Yukicoder Express Inc. announced that it would sell tickets that can be bought at a fixed price regardless of the travel distance, under the following 2 conditions.

• The route must not pass through the same station 2 or more times. (This includes the start and end points.)
• Any station can be the start or end point of a ticket.

Input

$N\ M$
$a_1\ b_1\ c_1$
$a_2\ b_2\ c_2$
$\vdots$
$a_M\ b_M\ c_M$

The first line contains the number of stations $N$ and the number of tracks $M$, separated by a space.
In the following $M$ lines, the $i$-th line contains the stations $a_i$,$b_i$ connected by the $i$-th track and the length $c_i$ of the track, separated by spaces.

Constraints

• All inputs are integers
• $2 \le N \le 16$
• $1 \le M \le 1000$
• $a_i \neq b_i$
• $1 \le c_i \le 10^5$

Output

Output the answer in one line.

Sample

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

8

7 5
1 3 5
3 4 7
1 2 10
5 7 14
6 7 10

24

10 9
9 2 4015
2 3 1869
4 3 2874
3 5 3255
5 7 4119
7 6 4874
5 8 4111
8 1 5238
8 10 4194

18488