The Problem

You want to make some presents for all your friends. The problem is that you cannot decide what to buy for each one.

There are a number of presents available to buy in the store, but there is only one item of each product. Each of them has a price and would be liked by some of your friends. You want to give to each of your friends one present that he/she likes, but you don't want to spend more money than necessary.

The Input

The input format is as follows:

An integer in a single line which says the number of problems to solve. Then, for each problem:

• An integer in a line by itself indicating the number of friends that you have (20 or less).

• An integer in a line by itself indicating the number of presents available in the store (25 or less). Then, for each present, a line containing a list of integers separated by spaces:

  • The price of the present.

  • The number of friends that like this present.

  • One integer for each of the friends that likes this present.

The Output

The output for each problem consists of one line with an integer indicating the price of the set of chosen presents, and then, for each friend, the number of the chosen present for him/her (all indices start from zero).

You should print only the cheaper solution, and if there are several cheaper solutions, the one that comes first in lexicographical order. If you cannot buy presents for each of your friends, you should print “No solution.”.

Sample Input

2
3
9
20 2 0 1
15 1 0
45 0
10 2 1 2
12 2 1 2
1400 3 0 1 2
100 2 0 2
10 1 2
10 2 1 2
4
4
5 1 0
4 1 1
3 1 2
2 1 1

Sample Output

35 1 3 7
No solution.