In the first line of the standard input, there is an integer Z (1<=Z<=50) , the number of data sets. The lines that follow contain the Z data sets.

The first line of each data set holds two integers, N and M , separated by a single space(1<=N,M<=100000) . These are the number of programmers working in the office and the number of statements recorded by Byteasar. The programmers are numbered from 1 to N.

Each of the m lines that follow describes a single statement. Each such line contains three integers , , and , separated by single spaces 1<=T<=M,1<=j<=N 0<=i<=N

These indicate that the programmer no. confessed that at time he was in the office and there were more programmers apart from him. We assume that the programmers came in to the office and left it at times different from those appearing in the statements, i.e., either before, after or in between them.