12
5 5
0 1 10
0 4 15
1 2 3
1 4 16
2 4 4
3 3
0 2 5
0 1 2
1 2 2
5 4
0 1 11
0 2 12
1 4 13
2 3 14 
4 4
0 1 1
1 3 1
0 2 1
2 3 1
100 180
0 1 1
0 10 1
1 2 1
1 11 1
2 3 1
2 12 1
3 4 1
3 13 1
4 5 1
4 14 1
5 6 1
5 15 1
6 7 1
6 16 1
7 8 1
7 17 1
8 9 1
8 18 1
10 11 1
10 20 1
11 12 1
11 21 1
12 13 1
12 22 1
13 14 1
13 23 1
14 15 1
14 24 1
15 16 1
15 25 1
16 17 1
16 26 1
17 18 1
17 27 1
18 19 1
18 28 1
20 21 1
20 30 1
21 22 1
21 31 1
22 23 1
22 32 1
23 24 1
23 33 1
24 25 1
24 34 1
25 26 1
25 35 1
26 27 1
26 36 1
27 28 1
27 37 1
28 29 1
28 38 1
30 31 1
30 40 1
31 32 1
31 41 1
32 33 1
32 42 1
33 34 1
33 43 1
34 35 1
34 44 1
35 36 1
35 45 1
36 37 1
36 46 1
37 38 1
37 47 1
38 39 1
38 48 1
40 41 1
40 50 1
41 42 1
41 51 1
42 43 1
42 52 1
43 44 1
43 53 1
44 45 1
44 54 1
45 46 1
45 55 1
46 47 1
46 56 1
47 48 1
47 57 1
48 49 1
48 58 1
50 51 1
50 60 1
51 52 1
51 61 1
52 53 1
52 62 1
53 54 1
53 63 1
54 55 1
54 64 1
55 56 1
55 65 1
56 57 1
56 66 1
57 58 1
57 67 1
58 59 1
58 68 1
60 61 1
60 70 1
61 62 1
61 71 1
62 63 1
62 72 1
63 64 1
63 73 1
64 65 1
64 74 1
65 66 1
65 75 1
66 67 1
66 76 1
67 68 1
67 77 1
68 69 1
68 78 1
70 71 1
70 80 1
71 72 1
71 81 1
72 73 1
72 82 1
73 74 1
73 83 1
74 75 1
74 84 1
75 76 1
75 85 1
76 77 1
76 86 1
77 78 1
77 87 1
78 79 1
78 88 1
80 81 1
80 90 1
81 82 1
81 91 1
82 83 1
82 92 1
83 84 1
83 93 1
84 85 1
84 94 1
85 86 1
85 95 1
86 87 1
86 96 1
87 88 1
87 97 1
88 89 1
88 98 1
9 19 1
19 29 1
29 39 1
39 49 1
49 59 1
59 69 1
69 79 1
79 89 1
89 99 1
90 91 1
91 92 1
92 93 1
93 94 1
94 95 1
95 96 1
96 97 1
97 98 1
98 99 1
100 179
0 1 1
0 10 1
1 2 1
1 11 1
2 3 1
2 12 1
3 4 1
3 13 1
4 5 1
4 14 1
5 6 1
5 15 1
6 7 1
6 16 1
7 8 1
7 17 1
8 9 1
8 18 1
10 11 1
10 20 1
11 12 1
11 21 1
12 13 1
12 22 1
13 14 1
13 23 1
14 15 1
14 24 1
15 16 1
15 25 1
16 17 1
16 26 1
17 18 1
17 27 1
18 19 1
18 28 1
20 21 1
20 30 1
21 22 1
21 31 1
22 23 1
22 32 1
23 24 1
23 33 1
24 25 1
24 34 1
25 26 1
25 35 1
26 27 1
26 36 1
27 28 1
27 37 1
28 29 1
28 38 1
30 31 1
30 40 1
31 32 1
31 41 1
32 33 1
32 42 1
33 34 1
33 43 1
34 35 1
34 44 1
35 36 1
35 45 1
36 37 1
36 46 1
37 38 1
37 47 1
38 39 1
38 48 1
40 41 1
40 50 1
41 42 1
41 51 1
42 43 1
42 52 1
43 44 1
43 53 1
44 45 1
44 54 1
45 46 1
45 55 1
46 47 1
46 56 1
47 48 1
47 57 1
48 49 1
48 58 1
50 51 1
50 60 1
51 52 1
51 61 1
52 53 1
52 62 1
53 54 1
53 63 1
54 55 1
54 64 1
55 56 1
55 65 1
56 57 1
56 66 1
57 58 1
57 67 1
58 59 1
58 68 1
60 61 1
60 70 1
61 62 1
61 71 1
62 63 1
62 72 1
63 64 1
63 73 1
64 65 1
64 74 1
65 66 1
65 75 1
66 67 1
66 76 1
67 68 1
67 77 1
68 69 1
68 78 1
70 71 1
70 80 1
71 72 1
71 81 1
72 73 1
72 82 1
73 74 1
73 83 1
74 75 1
74 84 1
75 76 1
75 85 1
76 77 1
76 86 1
77 78 1
77 87 1
78 79 1
78 88 1
80 81 1
80 90 1
81 82 1
81 91 1
82 83 1
82 92 1
83 84 1
83 93 1
84 85 1
84 94 1
85 86 1
85 95 1
86 87 1
86 96 1
87 88 1
87 97 1
88 89 1
88 98 1
9 19 1
19 29 1
29 39 1
39 49 1
49 59 1
59 69 1
69 79 1
79 89 1
90 91 1
91 92 1
92 93 1
93 94 1
94 95 1
95 96 1
96 97 1
97 98 1
98 99 1
4 5
0 1 1
0 2 100
1 2 1
2 3 1
1 3 100
42 80
0 2 10
2 41 7
0 3 9
3 41 6
0 4 7
4 41 2
0 5 8
5 41 6
0 6 9
6 41 3
0 7 3
7 41 10
0 8 8
8 41 7
0 9 3
9 41 7
0 10 4
10 41 4
0 11 6
11 41 5
0 12 7
12 41 9
0 13 8
13 41 11
0 14 5
14 41 2
0 15 7
15 41 11
0 16 9
16 41 3
0 17 11
17 41 6
0 18 8
18 41 6
0 19 11
19 41 2
0 20 3
20 41 7
0 21 5
21 41 8
0 22 3
22 41 8
0 23 2
23 41 10
0 24 9
24 41 3
0 25 7
25 41 2
0 26 4
26 41 4
0 27 2
27 41 8
0 28 8
28 41 5
0 29 6
29 41 7
0 30 11
30 41 11
0 31 11
31 41 11
0 32 3
32 41 2
0 33 7
33 41 9
0 34 9
34 41 6
0 35 5
35 41 5
0 36 2
36 41 7
0 37 6
37 41 5
0 38 2
38 41 9
0 39 5
39 41 7
0 1 1
1 41 1
0 40 1
40 41 1
100 183
0 1 1
0 10 1
0 5 1
5 89 1
99 90 1
1 2 1
1 11 1
2 3 1
2 12 1
3 4 1
3 13 1
4 5 1
4 14 1
5 6 1
5 15 1
6 7 1
6 16 1
7 8 1
7 17 1
8 9 1
8 18 1
10 11 1
10 20 1
11 12 1
11 21 1
12 13 1
12 22 1
13 14 1
13 23 1
14 15 1
14 24 1
15 16 1
15 25 1
16 17 1
16 26 1
17 18 1
17 27 1
18 19 1
18 28 1
20 21 1
20 30 1
21 22 1
21 31 1
22 23 1
22 32 1
23 24 1
23 33 1
24 25 1
24 34 1
25 26 1
25 35 1
26 27 1
26 36 1
27 28 1
27 37 1
28 29 1
28 38 1
30 31 1
30 40 1
31 32 1
31 41 1
32 33 1
32 42 1
33 34 1
33 43 1
34 35 1
34 44 1
35 36 1
35 45 1
36 37 1
36 46 1
37 38 1
37 47 1
38 39 1
38 48 1
40 41 1
40 50 1
41 42 1
41 51 1
42 43 1
42 52 1
43 44 1
43 53 1
44 45 1
44 54 1
45 46 1
45 55 1
46 47 1
46 56 1
47 48 1
47 57 1
48 49 1
48 58 1
50 51 1
50 60 1
51 52 1
51 61 1
52 53 1
52 62 1
53 54 1
53 63 1
54 55 1
54 64 1
55 56 1
55 65 1
56 57 1
56 66 1
57 58 1
57 67 1
58 59 1
58 68 1
60 61 1
60 70 1
61 62 1
61 71 1
62 63 1
62 72 1
63 64 1
63 73 1
64 65 1
64 74 1
65 66 1
65 75 1
66 67 1
66 76 1
67 68 1
67 77 1
68 69 1
68 78 1
70 71 1
70 80 1
71 72 1
71 81 1
72 73 1
72 82 1
73 74 1
73 83 1
74 75 1
74 84 1
75 76 1
75 85 1
76 77 1
76 86 1
77 78 1
77 87 1
78 79 1
78 88 1
80 81 1
80 90 1
81 82 1
81 91 1
82 83 1
82 92 1
83 84 1
83 93 1
84 85 1
84 94 1
85 86 1
85 95 1
86 87 1
86 96 1
87 88 1
87 97 1
88 89 1
88 98 1
9 19 1
19 29 1
29 39 1
39 49 1
49 59 1
59 69 1
69 79 1
79 89 1
89 99 1
90 91 1
91 92 1
92 93 1
93 94 1
94 95 1
95 96 1
96 97 1
97 98 1
98 99 1
100 184
0 1 1
0 10 1
0 5 1
5 89 1
10 90 1
90 99 1
1 2 1
1 11 1
2 3 1
2 12 1
3 4 1
3 13 1
4 5 1
4 14 1
5 6 1
5 15 1
6 7 1
6 16 1
7 8 1
7 17 1
8 9 1
8 18 1
10 11 1
10 20 1
11 12 1
11 21 1
12 13 1
12 22 1
13 14 1
13 23 1
14 15 1
14 24 1
15 16 1
15 25 1
16 17 1
16 26 1
17 18 1
17 27 1
18 19 1
18 28 1
20 21 1
20 30 1
21 22 1
21 31 1
22 23 1
22 32 1
23 24 1
23 33 1
24 25 1
24 34 1
25 26 1
25 35 1
26 27 1
26 36 1
27 28 1
27 37 1
28 29 1
28 38 1
30 31 1
30 40 1
31 32 1
31 41 1
32 33 1
32 42 1
33 34 1
33 43 1
34 35 1
34 44 1
35 36 1
35 45 1
36 37 1
36 46 1
37 38 1
37 47 1
38 39 1
38 48 1
40 41 1
40 50 1
41 42 1
41 51 1
42 43 1
42 52 1
43 44 1
43 53 1
44 45 1
44 54 1
45 46 1
45 55 1
46 47 1
46 56 1
47 48 1
47 57 1
48 49 1
48 58 1
50 51 1
50 60 1
51 52 1
51 61 1
52 53 1
52 62 1
53 54 1
53 63 1
54 55 1
54 64 1
55 56 1
55 65 1
56 57 1
56 66 1
57 58 1
57 67 1
58 59 1
58 68 1
60 61 1
60 70 1
61 62 1
61 71 1
62 63 1
62 72 1
63 64 1
63 73 1
64 65 1
64 74 1
65 66 1
65 75 1
66 67 1
66 76 1
67 68 1
67 77 1
68 69 1
68 78 1
70 71 1
70 80 1
71 72 1
71 81 1
72 73 1
72 82 1
73 74 1
73 83 1
74 75 1
74 84 1
75 76 1
75 85 1
76 77 1
76 86 1
77 78 1
77 87 1
78 79 1
78 88 1
80 81 1
80 90 1
81 82 1
81 91 1
82 83 1
82 92 1
83 84 1
83 93 1
84 85 1
84 94 1
85 86 1
85 95 1
86 87 1
86 96 1
87 88 1
87 97 1
88 89 1
88 98 1
9 19 1
19 29 1
29 39 1
39 49 1
49 59 1
59 69 1
69 79 1
79 89 1
89 99 1
90 91 1
91 92 1
92 93 1
93 94 1
94 95 1
95 96 1
96 97 1
97 98 1
98 99 1
43 63
16 15 7
37 42 1
27 17 1
13 34 1
24 29 1
36 3 1
20 13 7
31 42 1
32 30 1
3 25 1
23 25 7
7 36 5
8 2 1
30 21 1
26 27 1
40 11 1
33 32 5
38 35 1
14 22 1
2 26 1
31 37 1
27 14 7
6 15 1
25 31 1
22 32 1
12 23 1
1 41 5
29 16 1
41 24 1
5 28 1
3 37 5
4 6 1
2 17 5
10 1 1
35 9 1
39 26 7
28 7 1
34 9 7
9 5 1
16 4 1
30 19 5
0 40 7
5 12 7
19 18 1
33 14 1
17 33 1
0 10 1
22 21 7
18 38 5
7 12 1
15 39 1
18 13 1
6 8 5
20 19 1
23 36 1
24 4 5
21 20 1
11 29 7
34 38 1
35 28 5
11 41 1
1 40 1
39 8 1
33 53
7 10 5
21 23 7
0 2 7
20 21 1
25 28 5
4 7 5
18 20 7
29 30 1
27 29 7
19 22 5
22 25 5
10 11 1
24 26 7
25 26 1
12 13 1
7 8 1
16 17 1
31 32 1
1 4 5
8 9 1
15 17 7
28 29 1
5 6 1
17 18 1
6 8 7
26 27 1
3 4 1
16 19 5
11 12 1
30 32 1
3 5 7
22 23 1
10 13 5
9 10 1
6 7 1
24 25 1
4 5 1
28 31 5
2 3 1
14 15 1
1 2 1
0 1 1
21 22 1
23 24 1
27 28 1
13 14 1
15 16 1
13 16 5
18 19 1
30 31 1
19 20 1
9 11 7
12 14 7