Minieye published a notice on the Internet that whoever crack the password from some given information could have a chance to be offered a job. Pyy wants to have a try, because he heard that Minieye has a great team to investigate AI which he is interested in. The given information is as follows:

  There were N nonnegative numbers and the password is the largest one in them. And the only information about these N numbers were M formulas like Ai = Aj or Ai < Aj or Ai > Aj.

  Obviously, the answer is not unique. And pyy do not know how to solve it. So he wants to find an excellent ACMer to help him. He just need to know the smallest password so he can get the chance.

We have multiply cases. For each case:

The First line contains 2 numbers: N, M (1<=N<=1000, 1<=M<=10000)

From the second to (M+1)th line, each line contains 3 numbers: i, j, k

if k is equal 0, this formula is Ai = Aj

if k is equal -1, this formula is Ai < Aj

if k is equal 1, this formula is Ai > Aj

For each case, you should output the smallest password.

4 4
1 2 -1
2 3 0
2 4 -1
3 4 -1

2

A = {0, 1, 1, 2}