一般图最大权匹配

【题目描述】

给定一张有 $N$ 个顶点、$M$ 条边的带权简单无向图。第 $i$ 条边为 $(u_i, v_i)$，权值为 $w_i$。 求权值之和最大的匹配。

【输入】

$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)$ 为匹配中的边。

【输入样例】

7 8
2 0 1
0 5 2
5 6 3
6 1 4
1 0 5
1 3 6
3 4 7
1 4 8

【输出样例】

3 15
0 1
3 4
5 6

【输入样例2】

4 3
0 2 1
1 3 1
1 2 3

【输出样例2】

1 3
1 2

【数据范围】

• $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$

【来源】

Library Checker（yosupo06） general_weighted_matching

本题为 special judge（输出任意合法解），暂不可本地评测。