011 - 高速道路網の再編

問題文

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

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

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

課題

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

入力

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

$N \  M$
$u_{1} \  v_{1} \  c_{1}$
$u_{2} \  v_{2} \  c_{2}$
$\vdots$
$u_{M} \  v_{M} \  c_{M}$

$1$行目に地点の数$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} \neq vi \leq N)$、維持コスト$c_{i} \ (1 \leq c_{i} \leq 10,000)$が与えられる。

出力

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

入出力例

入力例1

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

出力例1

6

---

入力例2

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

出力例2

24

---