#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 :
40 23
1 2 1
2 3 1
1 4 0
1 5 1
5 6 1
5 7 1
6 8 1
5 9 0
4 10 1
3 11 1
3 12 0
3 13 1
1 14 1
8 15 0
15 16 1
3 17 1
12 18 0
6 19 1
11 20 1
6 21 0
16 22 1
18 23 0
3 24 1
16 25 0
19 26 0
4 27 1
27 28 1
25 29 0
21 30 0
16 31 1
3 32 0
29 33 0
7 34 1
2 35 0
9 36 0
8 37 0
24 38 1
1 39 0
21 40 0


// Output :
100378080

_________________________________________________________________________________________________________________
// Testcase : 4

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


// Output :
867766603

___________________________________________________________________________________________________________________________
// Testcase : 5

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


// Output :
533797318

__________________________________________________________________________________________________________________________
// Testcase : 6

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


// Output :
93454363
___________________________________________________________________________________________________________________________
// Testcase : 7

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


// Output :
982535631

___________________________________________________________________________________________________________________________
// Testcase : 8

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


// Output :
246329824

___________________________________________________________________________________________________________________________
// Testcase : 9

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


// Output :
829999817
___________________________________________________________________________________________________________________________
// Testcase : 10

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


// Output :
683651173
___________________________________________________________________________________________________________________________
// Testcase : 11

//Input :
37 22
1 2 1
1 3 1
1 4 0
4 5 0
2 6 0
5 7 1
7 8 1
2 9 0
3 10 0
8 11 1
2 12 1
4 13 1
8 14 1
12 15 1
1 16 0
3 17 1
12 18 1
2 19 1
3 20 1
14 21 1
1 22 0
10 23 0
14 24 1
8 25 0
1 26 0
7 27 1
21 28 1
20 29 0
18 30 0
9 31 1
30 32 1
23 33 1
11 34 1
14 35 0
10 36 0
14 37 0


// Output :
623262181
__________________________________________________________________________________________________________________________
// Testcase : 12

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


// Output :
98834063

___________________________________________________________________________________________________________________________