この問題は Python の想定解がTLEすることを確認しています。高速な言語へ変換することをお勧めします。
頂点に $1,2,\ldots,N$ の番号が、辺に $1,2,\ldots,M$ の番号がついた $N$ 頂点 $M$ 辺の単純無向グラフ $G$ が与えられます。 辺 $i$ は頂点 $u_i$ と頂点 $v_i$ を結び、重さは $w_i$ です。
極大マッチングの重さを、その極大マッチングに含まれる辺の重さの総和と定義します。 $G$ の極大マッチングの重さとして取りうる値のうち、最小の値を求めてください。
ここで、$G$ のマッチングとは、どの $2$ 辺も端点を共有しないような $G$ の辺の部分集合を指します。 また、$G$ の極大マッチングとは、$G$ のマッチングであって、 これ以上 $G$ のどの辺を追加してもマッチングではなくなるものを指します。
入力は以下の形式で標準入力から与えられます。
$N$ $M$ $u_1$ $v_1$ $w_1$ $u_2$ $v_2$ $w_2$ $\vdots$ $u_M$ $v_M$ $w_M$
答えを $1$ 行に出力してください。
5 5 1 2 3 1 3 2 1 4 -3 2 5 100 3 4 5
8
マッチング $\{\{1,2\},\{3,4\}\}$ は極大であり、重さが最小です。
20 0
0
20 1 1 2 -1000000000
-1000000000