5
3
9
1 1 1
1 2 1
1 3 1
2 1 1
2 2 1
2 3 1
3 1 1
3 2 1
3 3 1
3
9
1 1 1
1 2 5
1 3 1
2 1 1
2 2 1
2 3 1
3 1 1
3 2 1
3 3 1
3
9
1 1 1
1 2 5
1 3 1
2 1 1
2 2 1
2 3 1
3 1 10
3 2 1
3 3 1
5
8
1 5 10
1 3 8
1 1 4
2 2 4
3 3 4
4 4 4
5 5 4
5 1 11
30
36
1 1 3
2 2 1
3 2 2
5 2 10
4 4 3
5 8 4
6 6 2
8 6 3
9 10 3
10 9 3
10 11 1
13 11 2
13 13 1
13 15 3
15 15 1
11 17 15
17 16 2
17 17 1
18 18 1
18 19 2
20 19 3
20 21 2
21 20 1
22 21 1
23 18 5
23 20 1
23 25 2
24 23 1
26 23 3
27 23 4
27 27 3
28 28 1
29 29 1
29 30 3
30 25 3
30 27 2