给定一个包含 $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\,000\,000$

输入的第一行包含两个整数 $N$ 和 $M$。 接下来的 $M$ 行，每行包含三个整数 $u_i, v_i, w_i$，表示一条连接 $u_i$ 和 $v_i$、权重为 $w_i$ 的边。

输出的第一行包含两个整数 $X$ 和 $W$，分别表示最大匹配的边数和最大匹配的权重之和。 接下来的 $X$ 行，每行包含两个整数 $a_i, b_i$，表示匹配中的一条边。

样例

输入格式 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

输出格式 1

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