input:

741
5 3
1 5 3
3 4 2
1 4 3
4 3
2 4 2
1 4 1
2 3 3
10 3
9 10 2
3 6 3
1 9 1
3 4
2 3 2
1 3 2
2 3 3
1 3 3
10 4
6 6 1
9 10 2
4 8 3
4 10 3
6 3
1 4 3
2 4 2
2 2 2
4 3
1 4 1
1 1 2
2 3 1
5 3
4 5 2
4 5 1
1 4 3
9 3
2 3 2
1 9 2
2 4 2
4 3
1 3 3
2 3 2
1 2 3
8 4
5 8 1
4 8 1
3 5 3
1 3 3
9 3
4 5 1
1 5 3
3 8 2
8 3
5 7 2...

output:

60
3
3
3
3
3
3
3
1149
3
3
33
1953
3
3093
309
3
3
3
3
3
3
3
3
3
3
3
3
3
3
99
3
3
3
3
9
1461
3
3
3
45
3
3
3
2919
3
3
3
3
3
3
3
3
3
3
3
8751
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
1611
3
3
39
3
3
1305
3
3
3
3
3
3
3
9
3
3
3
3
3
3
3
219
3
3
3
3
3
3
3
3
21
3
3
3
3
3
3
3
3
9
813
3
3
3
3
3
3
3
3
3
3
3
...

result:

wrong answer 1st words differ - expected: '90', found: '60'