10 50
10 1 1
6 2 1
4 6 1
4 3 1
5 2 1
4 9 1
10 4 1
6 8 1
4 6 1
8 10 1
6 3 1
7 1 1
10 4 1
10 9 1
10 5 1
4 6 1
6 7 1
5 10 1
6 9 1
3 1 1
4 6 1
6 7 1
2 6 1
1 9 1
7 8 1
3 1 1
6 2 1
5 4 1
2 10 1
9 7 2
2 6 1
7 8 1
8 10 1
9 7 1
1 10 1
8 9 1
10 3 1
5 3 1
1 3 1
9 3 1
9 1 1
2 9 1
6 10 1
6 5 1
10 2 1
1 2 1
4 9 1
10 8 1
10 9 1
2 7 1