cho.sh

Frog Pushers

After channels are cut one by one in a fixed order, report the minimum spanning forest weight of the surviving graph before each cut, or FAIL if it is disconnected.

Medium6Union-findGraphMinimum spanning treeSortingNo attempts yetTime limit5sMemory limit512 MB

Problem

Task force Alpha X has been handed one mission: wipe out every frog and every frog pusher in the country within the next three to six months. Frogs are dangerous because they attack the communication channels between people. Once a frog attacks a channel, that channel is cut and can never be used again.

The task force has NN members, and there are CC communication channels among them. Two members exchange messages only while a surviving channel connects them, either directly or through other members.

The same pair of members may start out with several channels between them. Communicating over a channel carries risk. The channel may not be secure enough against hackers, or it may be physically tampered with and ruin the message. This risk is written as a risk index (RI), and every channel has its own RI value.

Sometimes an important message has to reach the whole group. It starts from one member, who sends it to a few others, and each member who receives it passes it on further. A member does not have to send the message to someone a less risky route already reaches. In the end every member must receive the message. The total risk index (TRI) of one group message is the sum of the RI of every channel used to carry it.

The task force wants the smallest possible TRI for each group message, and that minimum is called the LTRI. The LTRI is the same no matter who sends the message first. The intelligence squad has already worked out the order in which the frogs will attack the channels.

For each attack, compute the LTRI over the channels that are still alive immediately before it happens.

Input

The first line contains the number of test cases TT.

The first line of each test case contains the number of members NN and the number of channels alive at the start CC.

The next CC lines describe the channels in the order the frogs attack them. The ii-th of those lines contains three integers aa, bb, and rr, meaning a channel between member aa and member bb with risk index rr. It is possible that aa and bb are equal.

Constraints

  • 1≤N≤1001 \le N \le 100
  • 1≤C≤1051 \le C \le 10^5
  • 1≤T≤10001 \le T \le 1000, and the sum of CC over all test cases is at most 2×1052 \times 10^5
  • 1≤a,b≤N1 \le a, b \le N
  • 1≤r≤1091 \le r \le 10^9

Output

For each test case, first print a line of the form Case #X:, where XX is the test case number starting from 1.

Then print CC lines. The ii-th of those lines holds the LTRI immediately before the ii-th channel of the input is attacked. At that moment the first i−1i-1 channels are already cut and channels ii through CC are still alive. If a group message cannot reach every member, print FAIL on that line instead.