̈Gossipy gossiper, what did you get of so much gossiping? You set your soul into hell. Behold your great achievement! ̈ M.A. Hevia. Mermuradora. 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? Warning: “gossips” have nothing to do with “ghost ships”. Input The first line of the input contains an integer N, 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, that indicate the instants when G1 and G2 meet daily. For example, the pair: 372 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, ...). YoucanassumethatM≤20,K≤M∗M,andV ≤12. Output 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’. Sample Input 4 43 121 60 231
2/2 40 431 30 32 121 42 231 42 55 132 60 70 143 20 22 24 451 10 352 12 80 322 55 78 80 Sample Output 230 42 80 -1