Source: Library Checker

Statement

Given a simple weighted undirected graph with $N$ vertices and $M$ edges. $i$-th edge is $(u_i, v_i)$ with a weight $w_i$. Calculate the matching in which the sum of weights is maximized.

$N$ 頂点 $M$ 辺からなる単純重み付き無向グラフが与えられます。$i$ 番目の辺は $(u_i, v_i)$ を結ぶ重み $w_i$ の辺です。 重みの総和が最大であるようなマッチングをひとつ求めてください。

Constraint

• $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\,000\,000$

Input

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

Output

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

$X$ is the size of the maximum matching. $W$ is the maximum matching weight. $(a_i, b_i)$ is the edge of the matching.

$X$ はマッチングの辺の個数、$W$ はマッチングの重みの総和、$(a_i, b_i)$ はマッチングの辺です。

Example

Input 1

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

Output 1

3 15
0 1
3 4
5 6

Input 2

4 3
0 2 1
1 3 1
1 2 3

Output 2

1 3
1 2