Original problem statement (in Polish) can be found here.

Bronisław the Biologist loves his job. His research group carries out a lot of different experiments. Nobody knows exactly what purpose do they serve, but that doesn't stop him from having fun.

This time, specially trained hamster is the object of research for Bronisław. Scientists from his group have built an incredibly complicated racetrack made of transparent plastic - it consists of n nodes and m tunnels connecting those nodes. Tunnels have colours - some are red, some are green, others are striped red and green. Also, every tunnel has arrows painted on, denoting the direction of movement.

The experiment is as follows: hamster is dropped into the racetrack through one of the nodes. Then, he runs through the tunnels to his liking - he is specially trained to respect the direction of arrows. Moreover, at the very beginning he chooses a colour - red or green - and uses only the tunnels that have this colour (even if it's only partially).

Bronisław has a problem though. Hamster is incredibly stubborn - once he enters the racetrack, he will run without stopping, until he reaches a node where there is no way to choose a tunnel with colour he picked. Bronisław does not want to allow him to run for indefinitely long time, because the hamster can die from exhaustion. Biologist will have to remove some tunnels so that cannot happen.

Unfortunately, his colleagues did a really good job with building the racetrack. It's really sturdy, and to make matters worse some tunnels are interspersed with each other in fancy-looking patterns (perhaps they had too much fun with it). Some joints are harder to remove than others.

Help Bronisław in removing some tunnels in such a way that it's impossible for the hamster to run himself to death, no matter where he enters the racetrack, while doing as little work as possible.

Input

The first line contains a single integer t (t <= 10), denoting the number of testcases. Then, descriptions of the testcases follow.

First line of the description consists of two integers n and m - numbers of nodes and tunnels in a racetrack, respectively (1 <= n <= 30, 1 <= m <= 900). Nodes are numbered with consecutive integers, starting with 1.

In the next m lines there are descriptions of the tunnels, each one in a separate line. One such description consists of four integers a_i, b_i, w_i, k_i ( 1 <= a_i, b_i <= n, 1 <= w_i <= 10⁶, 1 <= k_i <= 3). It means that there is a one-directional tunnel from node a_i to a (different) node b_i and removing it will cost w_i units of work.

k_i denotes the colouring of the tunnel - 1 means it's green, 2 means it's red, 3 means it's striped red-green. There is at most one tunnel in one direction between each pair of nodes.

Output

For each testcase you should give a description of the racetrack modernization plan. Description begins with two integers p and q, denoting number of tunnels to remove and total amount of work to do so. (0 <= p <= m, 0 <= q). Then, q integers e_i should follow, denoting tunnel numbers that should be removed (1 <= e_i <= m). Tunnels are numbered according to their order from the input, starting with 1. Tunnel numbers in one testcase cannot repeat.

Example

Input:

1
4 7
1 2 5 1
2 3 8 3
3 1 5 1
1 3 5 2
4 2 5 2
3 4 5 2
4 3 1 2

Output:

2 9
2 7

Explanation

We remove tunnels 2-3 and 4-3, costing us 8+1=9. After removing those tunnels, the hamster will eventually stop running, no matter where he starts.

Scoring

If the plan is correct, and the cost q is computed correctly, it is worth q/(sum of all w_i in a testcase) points. Overall score is equal to the sum of individual scores. Score for the sample output is equal to 9/(5+8+5+5+5+5+1), about 0.26.