J :: Solar Power

Time Limit: 3 Seconds    Memory Limit: 131072 KB
Special Judge

Today, the increased consumption of energy in industrial societies has brought about irreversible environmental changes and renewable energy sources like solar power can play an important role toward eliminating these threats. The school of Electrical and Computer Engineering at University of Tehran, one of the pioneers in the field of renewable energies, has recently opened a new solar complex on campus. Their revolutionary solar panels will harness radiant light and heat from the sun and transform it to electrical energy. In addition to supplying the university infrastructure, they are planning to sell the excess amount of electricity to residential areas on the opposite side of North Kargar Street.
Tehran municipal authorities has provided several electrical cables from one side of the street to the other side.
Unfortunately, some of these cables cross each other and it is safe to say that the current passing through will cause serious damages to the network. Hence for each pair of crossing cables, we are only allowed to choose one.
In addition, each of these cables has a limit on how much current (Amperes∕Hour) it can let through without risking the network’s integrity. UT technicians are tasked with selecting a subset of these cables that maximizes the current in terms of A∕H. Write a program to help them achieve this goal.

Input

The input contains several test cases.
In the first line of input comes T (0 < T ≤ 100), the number of test cases.
For each test case, in the first line three positive integers m, n, and k are given which respectively denote the number of electrical pylons in the right side of street, the number of electrical pylons in the left side, and the total number of provided cables (m,n ≤ 1000 and k ≤ mn). Each of the following k lines contains three positive integers (i, j, and w, 1 ≤ i ≤ m, 1 ≤ j ≤ n) and one string (id) which represent the information of each cable; there is a cable with the name of id from electrical pylon i in the right side to the electrical pylon j of the left side with the maximum amount w Ampere per hour. There is at most one cable between each two nodes. Ids are unique strings containing only the lower case English alphabets with maximum length of 64.

Output

For each test case, print two lines. The first line contains the maximum amount of A∕h and the second one ids of selected cables which are separated with space. It should be noted that the ids should be printed in ascending alphabetical order.
If there is more than one possible solution, output any of them.

Sample Input

2
3 4 5
1 2 1 a
2 1 2 b
3 4 1 c
3 3 2 d
2 4 1 e
2 2 4
1 1 1 a
1 2 2 aa
2 1 3 aaa
2 2 4 aaaa

Sample Output

5
b c d
8
a aaa aaaa

Submit

Source: 12th Iran Nationwide Internet Contest - Final