H. Planar Triangles
time limit per test
6 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a weighted planar graph ($$$^{\text{∗}}$$$) with $$$n$$$ vertices and $$$m$$$ edges.

You are required to find two sets in it: a set $$$T$$$ of triangles ($$$^{\text{†}}$$$) and a set $$$S$$$ of edges such that:

  • Any two triangles in $$$T$$$ do not share an edge;
  • If all edges in $$$S$$$ are removed from the graph, there will be no triangles left;
  • $$$|S| \le 2|T|$$$;
  • The sum of the weights of the edges in $$$S$$$ does not exceed twice the sum of the weights of the triangles in $$$T$$$, where the weight of a triangle is the weight of its heaviest edge.

$$$^{\text{∗}}$$$Planar graph — a graph that can be drawn on a plane without edge intersections except at vertices.

$$$^{\text{†}}$$$A triangle is a triplet of vertices, each pair of which is connected by an edge

Input

Each test consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1023$$$) — the number of test cases. The following lines describe the test cases.

The first line of a test case contains two integers $$$n$$$, $$$m$$$ ($$$2 \le n \le 300\,000$$$, $$$0 \le m \le 3n-6$$$) — the number of vertices and edges in the graph, respectively. The vertices are numbered with integers from $$$1$$$ to $$$n$$$, and the edges are numbered with integers from $$$1$$$ to $$$m$$$.

The next $$$m$$$ lines contain the description of the edges; the $$$i$$$-th line contains three integers $$$a_i$$$, $$$b_i$$$, $$$w_i$$$ ($$$1 \le a_i \lt b_i \le n$$$, $$$1 \le w_i \le 10^9$$$), meaning that the $$$i$$$-th edge connects vertex $$$a_i$$$ with vertex $$$b_i$$$ and has weight $$$w_i$$$.

It is guaranteed that the graph is planar and does not contain loops or multiple edges.

The sum of $$$n$$$ across all test cases does not exceed $$$300\,000$$$.

Output

For each test case, output two non-negative integers $$$s$$$ and $$$t$$$ — the sizes of $$$S$$$ and $$$T$$$, respectively.

In the next $$$s$$$ lines, output the numbers $$$x_{i, 1}, x_{i, 2}$$$ ($$$1 \le x_{i,1}, x_{i,2} \le n$$$) — the endpoints of the $$$i$$$-th edge in the set $$$S$$$.

In the following $$$t$$$ lines, output the numbers $$$y_{j, 1}, y_{j, 2}, y_{j, 3}$$$ ($$$1 \le y_{j, 1}, y_{j, 2}, y_{j, 3} \le n$$$) — the vertices that make up the $$$j$$$-th triangle in the set $$$T$$$.

The edges in $$$S$$$ and the triangles in $$$T$$$, as well as the endpoints of the edges and the vertices of the triangles, can be output in any order.

Example
Input
2
3 3
1 2 1
1 3 1
2 3 1
4 6
1 2 1
1 3 1
1 4 1
2 3 1
2 4 1
3 4 1
Output
2 1
2 3
3 1
1 2 3
2 1
1 2
4 3
1 4 3