일반 가중 매칭

$N$개의 정점과 $M$개의 간선으로 이루어진 단순 가중 무방향 그래프가 주어진다. $i$번째 간선은 $(u_i, v_i)$이고 가중치는 $w_i$이다. 가중치 합이 최대가 되는 매칭을 구한다.

제약 조건

• $1 \leq N \leq 500$
• $0 \leq M \leq \frac{N(N-1)}{2}$
• $0 \leq u_i, v_i < N$
• $1 \leq w_i \leq 1\thinspace 000\thinspace 000$

$N$ $M$
$u_0$ $v_0$ $w_0$
$u_1$ $v_1$ $w_1$
:
$u_{M - 1}$ $v_{M - 1}$ $w_{M-1}$

$X$ $W$
$a_0$ $b_0$
$a_1$ $b_1$
:
$a_{X - 1}$ $b_{X - 1}$

$X$는 최대 매칭의 크기이다. $W$는 최대 매칭의 가중치이다. $(a_i, b_i)$는 매칭의 간선이다.