Warfare

In the year 2240 a great war is taking place between the Earth Allied Forces (EAF) and the Mars Federation (MF). Until recently neither side could gain the upper hand. Because of a recent financial crisis both factions' resources are thinning out, and the MF is using this to their advantage to claim more territory from the EAF. In response, the EAF has decided to carry out its greatest operation since the start of the war: a simultaneous attack against every MF base scattered across Mars. The EAF's forces consist mostly of mechs — huge bipedal, limbed vehicles with flying capabilities.

A typical MF base is built up as follows. The buildings that make up the base are positioned over one or more territories. Each territory is protected against outside attacks by an impenetrable energy field generated by shield towers positioned around it.

Each shield tower is connected to at least one other tower via channels built above the ground. When a set of connected towers forms a cycle, that cycle generates an energy field. However, if a channel in a cycle is destroyed so the cycle is broken, the energy field disappears. If all energy fields disappear, the base is easily overrun. Therefore the two towers connected by a channel protect it. Each tower can take down a given number of enemy mechs, and destroying a channel requires as many mechs as the two towers it connects can together take down. In other words, the cost to destroy a channel equals the sum of the two towers' values $u_i + u_j$. Two towers are connected by at most one channel, and no tower is connected to itself.

(a) Two towers connected by a channel. The vertices represent the towers while the line is the channel that connects them. The number of mechs needed to destroy the channel is the combined number of mechs the two connected towers can take down.

Attacking a channel on one side of a tower does not diminish how many mechs it can take down on its other channels; each channel's cost is the sum of its two towers independently.

(b) An MF base with multiple energy fields. The vertices represent the towers while the lines are the channels that connect them. Each number indicates how many mechs that tower can take down.

(c) In this case, destroying two channels makes all energy fields disappear. Four mechs are lost in the battle.

Because the operation is a surprise attack, all channels must be destroyed simultaneously — every channel is taken down at the same moment. All energy fields must be disabled in order to destroy an MF base. Tearing down every channel would achieve this but would sacrifice far too many mechs, and the EAF has very few to spare, so it must deploy its mechs as efficiently as possible.

Given the graph of shield towers, make every energy field disappear while losing the fewest EAF mechs (the total cost of the destroyed channels). Determine that minimum number of mechs lost.

The first line contains a positive integer $n$, the number of test cases. Each test case is given as follows:

• A line with a positive integer $m$ ($2 < m \le 100$), the number of towers in the base.
• Then, for each tower, two lines:
  • A line with three positive integers $i$ ($0 \le i \le m-1$), $u_i$ ($1 \le u_i \le 50$) and $c_i$ ($1 \le c_i \le m-1$), separated by spaces: the tower's (identification) number, how many mechs the tower can take down, and its number of channels.
  • A line with $c_i$ distinct integers, separated by spaces: the ids of the towers connected to tower $i$.

For each test case, print one line containing a single number: the minimum number of EAF mechs lost during the battle to make all energy fields disappear.