406713: GYM102503 J Mildly Irritated Gandhi

Rohatma Gandhi is the king of an archipelago. This archipelago consists of islands, all of which are under his reign. After building bridges between the islands and then destroying them, he became bored playing with his islands, and started wanting more. Through several nuclear threats, he claimed the Spratly Islands.

There are $$$n$$$ islands numbered $$$1, 2, \ldots, n$$$. Between them are $$$b$$$ bridges connecting pairs of islands, numbered $$$1, 2, \ldots, b$$$. The bridges are two-way bridges that can be crossed in either direction. Due to the inefficiency of the previous government who controlled the islands, some of these bridges may even connect the same pair of islands, and some bridges might even connect the same island to itself!

The poor infrastructure further increased Gandhi's aggression, and once again, he wanted to destroy several bridges by nuking them. The project manager originally in charge had several suggestions, however. She proposes that Gandhi can destroy as many bridges as he wants, but after destroying the bridges, it should be possible to travel from one island to any other island by crossing a series of bridges. Let's call any way Gandhi can destroy the maximum number of bridges while following the project manager's condition a max destruction. Note that every max destruction destroys the same number of bridges.

Another consideration is that each of the $$$n$$$ bridges has a certain amount of culture. The $$$i$$$th bridge has a culture value of $$$c_i$$$. After Gandhi destroys bridges, the sum of the culture values of the remaining bridges is called the total culture. The project manager computes $$$m$$$, which is the maximum possible total culture over all possible max destructions.

However, the project manager knows that some of Gandhi's citizens might protest (in a non-violent way). She is considering $$$q$$$ possibilities. In each possibility, the protest would ask for a certain set $$$S$$$ of the bridges to be kept, rather than be destroyed.

The project manager is now very stressed out, because she has to satisfy so many requirements. So she decides that she will instead do her best to partially satisfy protest, rather than follow it completely. In particular, for each of the $$$q$$$ possibilities, she wants to know the answer to the following: At most how many bridges in $$$S$$$ can be kept, if Gandhi destroys the maximum number of bridges, while the project manager's condition of travelling between islands is kept, while the total culture is still $$$m$$$?

The first line of input contains $$$t$$$, the number of test cases.

The first line of each test case contains two space-separated integers $$$n$$$ and $$$b$$$, the number of islands and the number of bridges.

Each of the next $$$b$$$ lines contains three space-separated integers $$$x_i$$$, $$$y_i$$$ and $$$c_i$$$, such that the $$$i$$$th bridge connects the isalnds $$$x_i$$$ and $$$y_i$$$ and has cultural value $$$c_i$$$.

The next line of the test case contains $$$q$$$, the number of protest possibilities.

The next $$$q$$$ lines contain each of the protest possibilities. In particular, the $$$i$$$th line contains $$$|S_i| + 1$$$ space-separated integers, the first of which is $$$|S_i|$$$, and the rest are the bridges in set $$$S_i$$$. ($$$|S_i|$$$ is defined as the number of bridges in $$$S_i$$$.)

For each of the $$$q$$$ possible protests, print a single line containing an integer denoting the answer.

$$$1 \le t \le 616$$$

$$$1 \le n \le 66666$$$

$$$1 \le b \le 133332$$$

The sum of the $$$n$$$s is $$$\le 66666$$$.

The sum of the $$$b$$$s is $$$\le 133332$$$.

$$$q \ge 1$$$.

$$$0 \le c_i \le 133332$$$

$$$1 \le x_i, y_i \le n$$$

$$$|S_i| \ge 1$$$.

The sum of the $$$|S_i|$$$s in a single test case is $$$\le b$$$.

The elements of $$$S_i$$$ are distinct.

$$$1 \le j \le b$$$ for every $$$j$$$ in $$$S_i$$$.

It is possible to go from any island to any other island using the bridges.

Subtask 1 (30 points):

The sum of the $$$n$$$s is $$$\le 1000$$$.

The sum of the $$$b$$$s is $$$\le 2000$$$.

Subtask 2 (4 points):

The sum of the $$$n$$$s is $$$\le 4000$$$.

The sum of the $$$b$$$s is $$$\le 8000$$$.

Subtask 3 (6 points):

The $$$c_i$$$s are distinct.

$$$|S_i| = 1$$$

Subtask 4 (6 points):

The $$$c_i$$$s are distinct.

Subtask 5 (26 points):

$$$|S_i| = 1$$$

Subtask 6 (28 points):

No additional constraints.

1
4 4
1 3 40
3 4 20
1 2 30
2 4 10
2
2 2 4
2 2 3

1
2