Gossiping mechanism is quite simple, but effective. Everything starts with a master gossiper (most probably a she), who hears, witnesses, or makes up some extraordinary news. Whenever she meets another person, she tells him the news. As soon as these people meet others, they tell them the news. Soon, everybody is informed of the news, and the process finishes. Gossipers meet each other daily at the same hours. We have information on when every pair of gossipers meet. For simplicity, days are divided into 100 instants. The first day goes from 0 to 99, the second from 100 to 199, and so on. Suppose the gossiping process starts at time 0. When will it finish? That is, when will all the people be informed of the news?
The first line of the input contains an integer N (≤ 40), indicating the number of test cases.
For each test case, the first line contains two integers M and K. M indicates the number of people in this case (numbered from 1 to M). The master gossiper is always number 1. K indicates the number of pairs of people who meet.
Next, we have 2K lines (two lines for each pair of people who meet). The first line of each pair contains three integers, G1, G2 and V. This line means that gossipers G1 and G2 meet V times a day. The second line contains V numbers from 1 to 99, which indicate the instants when G1 and G2 meet daily.
For example, the pair:
3 7 2
28 88
means: person 3 and person 7 meet twice a day, at instants 28 and 88 everyday (that is, at 28, 88, 128, 188, 228, 288, ...).
You can assume that M ≤ 20, K ≤ M * M, and V ≤ 12. Also, any (G1, G2) pair appears at most once in each test case.
For each test case, the output should consist of a single integer F in one line, indicating the instant when the process finishes. If the process does not finish (for example, there is some isolated person who will never be informed), the result should be ‘−1’.