問題文

ここに0番〜(N-1)番の品物がある。
また、
item1 item2 score
という形式で書かれた得点表がある。
品物を並べた時、item1がitem2よりも前であればscore点を獲得できるという意味である。

得点表が与えられるので、品物を適切に並び替えた時、獲得できる得点を最大化したい。そのときの得点を出力せよ。

注意：LL系の言語だと工夫しないといけないかもしれません。

入力

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

N:品物の数
M:得点表の行数
item1[i] item2[i] score[i] (1<=i<=M): 品物1、品物2、得点

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

得点表の相異なる行において、item1とitem2がどちらも等しくなることはない。

出力

獲得できる最大得点を出力せよ。出力後は改行すること。

サンプル

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