Problem Statement

There are items numbered 0 to (N-1).
There is also a score table written in the format
item1 item2 score
Each line 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 arranging the items appropriately. Output that score.

Note: In LL languages, you may need to be careful to make your solution fast enough.

Input

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

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

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

No two different lines of the score table have both item1 and item2 equal.

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