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

Constraints

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

The input is given in the following format:

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

Output

The output should be in the following format:

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

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

Examples

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