#Testcases by Samkit Lodha
#Testcases for count of magical sequences

___________________________________________________________________________________________________________________________
// Testcase : 1

//Input :
4 4
1 2 1
2 3 1
3 4 1


// Output :
252

___________________________________________________________________________________________________________________________
// Testcase : 2

//Input :
3 5
1 2 1
1 3 0



//Output :
210

___________________________________________________________________________________________________________________________
// Testcase : 3

//Input :
12 7
1 2 1
1 3 0
2 4 1
3 5 0
5 6 0
3 7 0
3 8 0
2 9 0
6 10 0
7 11 1
2 12 1


// Output :
35008134

_________________________________________________________________________________________________________________
// Testcase : 4

//Input :
26 20
1 2 1
1 3 0
2 4 0
4 5 1
3 6 0
6 7 1
6 8 1
8 9 1
4 10 0
4 11 0
1 12 1
7 13 1
10 14 0
1 15 1
10 16 0
5 17 1
9 18 0
7 19 0
16 20 1
20 21 0
5 22 1
3 23 1
10 24 0
10 25 1
16 26 1


// Output :
124626085
___________________________________________________________________________________________________________________________
// Testcase : 5

//Input :
60 59
1 2 1
1 3 0
2 4 0
4 5 0
2 6 0
1 7 0
4 8 1
1 9 1
5 10 1
9 11 0
2 12 0
5 13 1
1 14 1
10 15 1
2 16 1
9 17 0
3 18 1
11 19 1
13 20 1
5 21 0
15 22 1
16 23 1
20 24 0
12 25 1
25 26 0
4 27 1
27 28 0
1 29 0
13 30 0
10 31 1
5 32 0
28 33 1
25 34 0
25 35 0
30 36 0
23 37 1
5 38 1
1 39 1
38 40 1
17 41 0
16 42 0
10 43 1
11 44 0
6 45 0
27 46 0
25 47 1
34 48 1
4 49 0
18 50 1
16 51 1
50 52 1
12 53 0
21 54 1
2 55 1
38 56 1
55 57 1
54 58 1
8 59 0
19 60 0


// Output :
208089035
__________________________________________________________________________________________________________________________
// Testcase : 6

//Input :
12 9
1 2 0
1 3 0
1 4 0
4 5 1
3 6 1
3 7 1
6 8 0
3 9 1
8 10 1
5 11 1
2 12 0


// Output :
157826675
___________________________________________________________________________________________________________________________
// Testcase : 7

//Input :
74 57
1 2 1
2 3 0
1 4 0
4 5 0
3 6 0
4 7 0
6 8 0
1 9 1
7 10 1
4 11 0
8 12 1
2 13 0
9 14 1
5 15 1
5 16 0
12 17 0
7 18 0
16 19 1
18 20 0
6 21 1
19 22 0
15 23 0
22 24 0
1 25 0
16 26 1
3 27 1
27 28 1
23 29 0
8 30 0
15 31 1
29 32 1
1 33 0
23 34 1
34 35 0
31 36 0
23 37 0
28 38 1
1 39 0
11 40 1
3 41 1
26 42 1
2 43 1
33 44 0
15 45 0
34 46 0
5 47 1
27 48 0
3 49 0
30 50 0
14 51 1
7 52 1
11 53 0
36 54 0
44 55 0
17 56 0
56 57 0
48 58 0
55 59 0
29 60 0
26 61 0
52 62 0
35 63 1
58 64 0
59 65 0
56 66 0
40 67 1
39 68 0
68 69 0
12 70 1
44 71 0
3 72 1
5 73 0
14 74 1


// Output :
990047674
___________________________________________________________________________________________________________________________
// Testcase : 8

//Input :
85 41
1 2 0
2 3 1
2 4 0
2 5 0
4 6 0
3 7 1
1 8 1
5 9 0
1 10 0
5 11 0
6 12 0
4 13 0
3 14 0
3 15 1
13 16 1
3 17 0
1 18 0
2 19 0
15 20 1
16 21 0
10 22 0
15 23 0
11 24 1
10 25 1
20 26 1
19 27 1
14 28 0
2 29 0
12 30 0
22 31 0
15 32 0
26 33 1
31 34 1
15 35 0
4 36 0
21 37 0
23 38 0
34 39 1
14 40 0
4 41 1
41 42 0
36 43 0
23 44 0
42 45 0
18 46 0
12 47 1
1 48 1
26 49 0
22 50 1
12 51 0
17 52 0
11 53 1
19 54 1
51 55 0
20 56 1
43 57 1
37 58 0
53 59 1
18 60 0
13 61 0
25 62 1
35 63 0
6 64 1
41 65 0
22 66 1
17 67 0
44 68 1
8 69 0
32 70 0
24 71 1
18 72 1
14 73 1
3 74 1
59 75 0
41 76 1
70 77 1
75 78 1
11 79 0
48 80 1
65 81 1
70 82 0
48 83 0
38 84 0
15 85 1


// Output :
337240913
___________________________________________________________________________________________________________________________
// Testcase : 9

//Input :
73 4
1 2 1
1 3 0
2 4 0
3 5 0
1 6 1
3 7 0
6 8 1
2 9 1
4 10 0
2 11 0
3 12 0
4 13 1
13 14 0
11 15 0
8 16 0
13 17 0
11 18 1
15 19 1
18 20 1
12 21 1
4 22 0
1 23 0
10 24 0
11 25 0
18 26 1
20 27 1
1 28 0
10 29 1
28 30 1
25 31 0
28 32 1
32 33 1
33 34 0
28 35 0
10 36 1
22 37 0
25 38 1
32 39 0
5 40 0
1 41 0
32 42 0
8 43 1
11 44 1
32 45 1
10 46 0
19 47 1
38 48 0
4 49 0
22 50 1
28 51 1
43 52 1
51 53 1
34 54 0
4 55 0
24 56 1
22 57 1
53 58 1
12 59 1
30 60 0
23 61 1
11 62 1
31 63 0
32 64 0
3 65 1
30 66 1
5 67 0
46 68 0
56 69 1
67 70 0
51 71 1
42 72 0
32 73 1


// Output :
28326016
___________________________________________________________________________________________________________________________
// Testcase : 10

//Input :
72 36
1 2 1
2 3 1
1 4 0
2 5 0
2 6 0
6 7 1
5 8 1
4 9 0
9 10 1
2 11 1
9 12 0
1 13 1
8 14 0
10 15 1
3 16 1
14 17 1
15 18 0
4 19 1
6 20 0
11 21 1
3 22 0
21 23 0
14 24 1
4 25 1
12 26 1
12 27 1
2 28 0
25 29 1
20 30 1
4 31 0
29 32 1
31 33 0
10 34 1
15 35 1
23 36 0
29 37 0
22 38 1
37 39 1
38 40 1
31 41 0
29 42 1
21 43 1
32 44 1
6 45 0
31 46 1
34 47 0
2 48 1
22 49 0
28 50 1
43 51 1
3 52 1
30 53 1
47 54 0
18 55 0
18 56 0
36 57 1
7 58 0
28 59 1
55 60 0
19 61 0
30 62 1
27 63 0
6 64 1
11 65 1
62 66 0
36 67 1
54 68 1
44 69 0
53 70 1
59 71 0
11 72 1


// Output :
728361741
___________________________________________________________________________________________________________________________
// Testcase : 11

//Input :
70 49
1 2 1
1 3 1
2 4 0
2 5 0
5 6 1
5 7 1
1 8 1
8 9 1
6 10 1
7 11 1
6 12 0
10 13 0
6 14 1
1 15 1
7 16 1
9 17 0
13 18 1
10 19 1
15 20 1
19 21 0
6 22 0
2 23 0
15 24 0
20 25 1
4 26 1
3 27 1
5 28 1
26 29 1
1 30 0
19 31 0
26 32 1
8 33 1
25 34 1
30 35 1
27 36 0
19 37 1
4 38 0
16 39 1
12 40 1
16 41 1
29 42 1
10 43 1
15 44 0
39 45 0
10 46 1
39 47 0
46 48 1
19 49 1
10 50 0
42 51 0
41 52 1
48 53 0
24 54 0
15 55 1
43 56 0
20 57 1
8 58 1
22 59 0
34 60 1
26 61 0
49 62 1
60 63 0
48 64 1
18 65 0
44 66 1
37 67 1
28 68 0
27 69 0
35 70 0


// Output :
431936811
__________________________________________________________________________________________________________________________
// Testcase : 12

//Input :
58 21
1 2 0
1 3 0
1 4 1
3 5 0
1 6 0
4 7 0
7 8 0
6 9 0
8 10 1
3 11 0
4 12 0
7 13 0
8 14 0
9 15 1
1 16 1
3 17 0
15 18 0
5 19 1
6 20 1
15 21 1
13 22 0
10 23 1
7 24 1
20 25 0
19 26 1
4 27 1
19 28 0
6 29 0
15 30 1
30 31 0
9 32 0
14 33 1
27 34 0
34 35 1
33 36 1
28 37 1
7 38 0
26 39 1
4 40 1
5 41 0
11 42 1
31 43 1
3 44 0
29 45 0
2 46 1
1 47 1
37 48 1
46 49 1
24 50 0
8 51 1
16 52 0
27 53 0
39 54 1
22 55 0
35 56 0
54 57 0
24 58 1


// Output :
109345925
___________________________________________________________________________________________________________________________