問題文

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

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

※ http://yukicoder.me/problems/209
の制約強化版です。

入力

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

$N$:品物の数
$M$:得点表の行数
$item1_i\ item2_i\ score_i (1 \le i \le M)$: 品物1、品物2、得点

制約
$30<=N<=50$
$1<=M<=N*(N-1)$
$0<=item1,item2 < N$
$item1!=item2$
$1<=score<=10000$
得点表の相異なる行において、item1とitem2がどちらも等しくなることはない。

出力

Total_Score
ordered_item[1] ... ordered_item[N]

$Total\_Score$:合計得点
$ordered\_item_i\ (1 \le i \le N)$: i番目に並べるべき品物 品物iを並べる場所ではありませんので注意して下さい。

出力について

以下の条件をすべて満たす時、ACとなります。

• 出力要素がN+1個(以上)
• 想定解のプログラムを100回動かして得られた得点の最大値をXとして、Total_ScoreがX*4/5 9/10以上 (※0:00変更)
• ordered_itemに重複がない
• ordered_itemにしたがって計算した結果がTotal_Scoreと等しい

サンプル

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
3 2 1 0
(this_is_garbage)