Mr. V and Mr. I are playing a thrilling game.

The game takes place on a circle with $2n$ intelligence stations, labeled clockwise from $0, 1, \dots, 2n-1$. Stations with odd labels are controlled by Mr. V, while the others are controlled by Mr. I.

The game is set against the backdrop of intelligence transmission. Mr. I has learned that Mr. V has connected $m$ communication lines between the stations he controls. The $i$-th communication line can be viewed as a line segment connecting two points $u_i$ and $v_i$, with a communication strength of $s_i$. Mr. I wishes to disrupt these communication lines. To do so, he can emit several interference light waves. Each interference light wave requires specifying two distinct intelligence stations $x$ and $y$ (controlled by Mr. I) as the source and receiver, and an interference strength $w$. Thus, an interference light wave can be viewed as a line segment connecting points $x$ and $y$ with weight $w$.

For a communication line with strength $s$, let $T$ be the set of interference light waves that intersect it. The communication line is considered disrupted if and only if $\sum_{j \in T} w_j \ge s$.

Mr. I wants to disrupt all of Mr. V's communication lines. However, emitting interference light waves is a very tiring task, so he wants to emit a set of suitable interference light waves such that the sum of the interference strengths of these waves is minimized. Naturally, this problem is handled by you, his military advisor. Please help Mr. I calculate the minimum sum of interference strengths and provide a feasible construction.

Input

The input is read from standard input.

The first line contains two integers $n$ and $m$, as described in the problem.

The next $m$ lines each contain three integers $u_i, v_i, s_i$, representing that the $i$-th communication line connects intelligence stations $u_i$ and $v_i$ with communication strength $s_i$. It is guaranteed that $0 \le u_i, v_i < 2n$, $1 \le s_i \le 10^3$, and both $u_i$ and $v_i$ are odd.

Output

The output is written to standard output.

The first line should output an integer $A$, representing the minimum sum of interference strengths.

The next line should output an integer $C$, representing the number of interference light waves you emit.

Let the light waves in your solution be $\{(x_i, y_i, w_i)\}$. The next $C$ lines should each contain three space-separated integers. The three numbers in the $i$-th line represent $x_i, y_i, w_i$ respectively.

You must ensure the following conditions are met for your construction to be recognized:

• $0 \le C \le 10^5$.

• For all $1 \le i \le C$:

  • $0 \le x_i, y_i < 2n, w_i > 0$.
  • $x_i, y_i$ are both even and $x_i \ne y_i$.
  • $\sum_{i} w_i \le A$.

Please note: If your construction is not recognized, we do not guarantee that you will receive any partial points for the test case.

Examples

Input 1

5 4
1 7 1
9 7 1
3 9 1
5 3 1

Output 1

2
2
2 8 1
4 6 1

Note 1

As shown in the figure below, since all communication strengths and interference strengths are $1$, they are omitted in the diagram. Here, green dots represent intelligence stations controlled by Mr. V, red dots represent intelligence stations controlled by Mr. I, solid lines represent communication lines, and dashed lines represent interference light waves. Note that the feasible solution is not unique.

Subtasks

• For 25% of the data, $N \le 100, M \le 400$.
• For another 25% of the data, $N \le 500, M \le 10^3$, where 5% of the data also satisfies $s_i = 1$.
• For another 25% of the data, $N \le 500, M \le 10^4$, where 10% of the data also satisfies $s_i = 1$.
• For another 25% of the data, $N \le 2000, M \le 4000$, where 10% of the data also satisfies $s_i = 1$.

After submitting your code, the pretest data will be evaluated and the results returned. This problem's pretest data contains 20 test cases, each with the same $N, M, s_i$ constraints as the corresponding final test cases.

Note: The evaluation results of the pretest data have no relation to the final evaluation results.

Scoring

For each test case, if your program correctly calculates $A$ (the minimum sum of interference strengths), you receive 3 points. If, in addition to this, you provide a correctly formatted construction that meets the requirements, you receive 5 points.