Problem Statement

There are items numbered 0 to (N-1).
There is also a score table whose rows are written in the format
item1 item2 score
.
This means that when the items are arranged, score points are obtained if item1 comes before item2.

Given the score table, you want to maximize the points obtained by rearranging the items appropriately. Output that score.

Input

N M
item1[1] item2[1] score[1]
…
item1[M] item2[M] score[M]

N: the number of items
M: the number of rows in the score table
item1[i] item2[i] score[i] (1<=i<=M): item 1, item 2, score

Constraints
2<=N<=14
1<=M<=N*(N-1)
0<=item1,item2<N
item1!=item2
1<=score<=10000

No two distinct rows of the score table have both the same item1 and the same item2.

Output

Output the maximum score that can be obtained. Print a newline after the output.

Sample

4 9
0 1 1
0 2 2
0 3 3
1 2 4
1 3 5
2 3 6
3 2 100
2 1 100
1 0 100

300