高速道路網の再編

ヅイア国の高速道路網は、都市(地点)とそれらを結ぶ道路から構成されています。この高速道路網は以下の条件を満たすように建設されています。

• 1から$N$の番号が割り当てられた$N$個の都市（地点）がある。
• 道路は一方通行で、ある地点とある地点を直接結ぶ道路は多くても２つしかない（２つあるときは互いに逆向き）。
• どの地点からも、他のすべての地点へ必ずたどり着くことができる。

高速道路網を維持するには、道路ごとにコストがかかります。財政難を避けるため、ヅイア国はいくつかの道路を廃止することに決め、あなたを担当者に指名しました。あなたは、上の条件は変えずに、高速道路網全体の維持コストが最小になるように再編しなければなりません。

地点の数と道路の情報が与えられたとき、再編後の高速道路網全体の維持コストの最小値を求めるプログラムを作成せよ。

入力

入力は以下の形式で与えられる。

$N$ $M$
$u_1$ $v_1$ $c_1$
$u_2$ $v_2$ $c_2$
:
$u_M$ $v_M$ $c_M$

１行目に地点の数$N$ ($2 \leq N \leq 13$)と道路の数$M$ ($N \leq M \leq N \times (N-1)$)が与えられる。続く$M$行に$i$番目の道路の出発地点$u_i$と到着地点$v_i$ ($1 \leq u_i \ne v_i \leq N$)、維持コスト$c_i$ ($1 \leq c_i \leq 10,000$)が与えられる。

出力

再編後の高速道路網全体の維持コストの最小値を１行に出力する。  

入出力例

入力例１

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

出力例１

6

入力例２

5 8
1 2 7
1 5 2
2 1 8
2 3 3
3 4 5
4 5 8
5 1 5
5 2 1

出力例２

24

 

Note

Algorithm

 

---