E: 敵襲から守れ

問題

島が $V$ 島あり、それぞれ $0, 1, ..., V-1$ と番号がついている。橋が $E$ 本あり、それぞれ $0, 1, ..., E-1$ と番号がついている。 $i$ 番目の橋は島 $s_i$ と島 $t_i$ にかかってあり、幅は $c_i$ である。

島 $0$ に基地があるAORイカちゃん軍団 (通称イカ団) は規模が弱小であるため、島 $V-1$ にあるSosu-Usa軍団 (通称そすうさ団) にいつもやられっぱなしである。ある日、イカ団は「そすうさ団が明日攻めてくる」との情報を得た。そすうさ団の基地から大人数のそすうさ団の部下が橋を渡って島を移動し、部下が一人でもイカ団の基地にたどり着かれるとイカ団は滅びてしまう……。

そこでイカ団は橋に通行止めテープを張ることで橋を通れないようにし、危機を免れようとした。使うテープの長さは通行止めにした橋の幅の総和である。また、そすうさ団の部下全員が必ずある一本の幅 $1$ の橋を通る場合、イカ団がそこで待ち伏せすることで、そすうさ団を通れなくすることができる。

保持しているテープの長さは $10^4$ である。今後のことも考え、消費するテープの量はなるべく少なくしたい。そすうさ団の部下がイカ団の基地にたどり着けないようにするために使うテープの長さの最小値を求めよ。ただし、テープの長さが足りずどうしても攻められてしまう合は $-1$ を出力せよ。

制約

• $2 \le V \le 5 \times 10^3$
• $1 \le E \le min(5 \times 10^3, V(V-1)/2)$
• $1 \le c_i \le 5 \times 10^3$
• $0 \le s_i, t_i \lt V$
• 与えられるグラフは連結かつ単純である。
• 入力は全て整数で与えらえる。

入力形式

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

$V \ E$
$s_0 \ t_0 \ c_0$
$s_1 \ t_1 \ c_1$
$\vdots$
$s_{E-1} \ t_{E-1} \ c_{E-1}$

出力

そすうさ団の部下がイカ団の基地にたどり着けないようにするために使うテープの長さの最小値を出力せよ。ただし、テープの長さが足りずどうしても攻められてしまう場合は $-1$ を出力せよ。また、末尾に改行も出力せよ。

サンプル

サンプル入力 1

4 4
0 1 3
0 2 4
1 3 1
2 3 5

サンプル出力 1

4

イカ団は $2$ 番目の橋で待ち伏せし、$1$ 番の橋にテープを貼ることで、そすうさ団を止められる。

サンプル入力 2

2 1
0 1 100

サンプル出力 2

100

$0$ 番目の橋にテープを貼ることで、そすうさ団を止められる。 橋の幅が $1$ でないため、待ち伏せはできない。

サンプル入力 3

5 6
0 1 5000
0 2 5000
0 3 5000
1 4 5000
2 4 5000
3 4 5000

サンプル出力 3

-1

テープが足りないため、どのようにテープを貼ってもそうすさ団は止められない。

Note

Commentary

 

---