题目描述

现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。

输入格式

第一行包含两个数，n 和 m，表示该无向图的节点数和边数，每个节点用 1～n 的整数编号；

接下来的 m 行，每行包含三个整数：a,b,c，表示节点 a,b 之间的边的权值为 c。

输出格式

输出不同的最小生成树有多少个。你只需要输出数量对 31011 的模就可以了。

4 6
1 2 1
1 3 1
1 4 1
2 3 2
2 4 1
3 4 1

8

100 1000
1 2 2
1 9 2
1 14 1
1 27 2
1 28 2
1 31 1
1 39 2
1 41 2
1 42 4
1 46 4
1 53 4
1 68 4
1 74 4
1 75 4
1 80 4
1 82 4
1 83 5
1 84 5
1 87 5
1 89 6
1 90 6
1 92 5
1 100 5
2 3 6
2 5 8
2 10 8
2 15 8
2 19 7
2 31 7
2 33 8
2 34 8
2 47 8
2 48 10
2 52 10
2 56 10
2 58 10
2 62 10
2 65 10
2 67 9
2 79 10
2 86 11
2 87 12
2 88 12
2 95 11
3 4 11
3 13 12
3 18 12
3 23 12
3 30 14
3 33 14
3 35 13
3 41 13
3 47 14
3 60 14
3 64 13
3 72 13
3 74 15
3 78 16
3 89 16
3 91 16
3 92 16
3 93 16
3 94 15
3 95 16
3 99 17
4 6 17
4 7 17
4 12 17
4 23 18
4 34 17
4 38 18
4 48 17
4 51 19
4 53 20
4 64 20
4 67 20
4 74 20
4 78 19
4 79 20
4 80 19
4 86 22
4 92 21
4 93 21
4 95 22
4 99 22
5 6 22
5 7 22
5 11 21
5 29 23
5 31 23
5 39 24
5 44 24
5 51 24
5 55 23
5 59 24
5 61 24
5 73 25
5 80 26
5 82 26
5 83 25
5 92 26
6 9 26
6 15 26
6 16 25
6 18 27
6 19 28
6 20 28
6 21 28
6 31 28
6 35 27
6 39 27
6 47 28
6 49 29
6 51 30
6 57 30
6 63 29
6 86 29
6 95 30
6 100 30
7 8 29
7 13 32
7 20 31
7 24 32
7 26 31
7 35 31
7 37 31
7 40 32
7 41 31
7 47 34
7 48 34
7 55 34
7 58 34
7 61 34
7 62 33
7 68 33
7 70 34
7 73 35
7 82 36
7 83 35
7 87 35
7 94 36
7 96 35
7 98 36
8 15 35
8 16 37
8 24 38
8 32 38
8 33 38
8 45 37
8 50 38
8 57 37
8 58 38
8 59 39
8 61 39
8 65 39
8 68 39
8 74 40
8 77 40
8 78 39
8 80 39
8 94 42
8 98 42
8 99 41
9 13 42
9 32 42
9 34 42
9 35 42
9 45 41
9 47 44
9 49 44
9 51 43
9 53 44
9 55 44
9 58 43
9 67 43
9 75 43
9 81 45
9 92 46
9 93 46
10 13 45
10 14 45
10 17 46
10 27 45
10 28 46
10 29 48
10 37 47
10 38 48
10 47 48
10 52 47
10 54 47
10 56 48
10 60 48
10 71 49
10 76 50
10 77 49
10 87 50
10 100 49
11 17 50
11 24 50
11 27 50
11 31 51
11 34 52
11 37 51
11 40 52
11 52 52
11 57 51
11 65 51
11 68 51
11 73 54
11 85 53
11 88 53
11 91 53
11 97 54
11 99 54
12 13 53
12 20 53
12 24 56
12 27 56
12 28 56
12 33 55
12 34 56
12 38 56
12 44 55
12 51 55
12 55 57
12 58 57
12 62 57
12 63 57
12 64 57
12 68 58
12 72 57
12 78 57
12 79 60
12 80 59
12 85 60
12 86 60
12 88 59
12 92 60
12 95 59
12 100 59
13 14 62
13 20 62
13 28 61
13 31 61
13 33 62
13 42 62
13 45 61
13 54 61
13 55 63
13 56 64
13 57 63
13 69 64
13 76 64
13 77 63
13 78 63
13 93 64
13 94 65
13 98 65
13 100 66
14 24 65
14 27 66
14 33 65
14 36 65
14 38 66
14 43 68
14 51 68
14 52 68
14 73 67
14 75 68
14 82 67
14 83 67
14 91 67
14 92 69
14 96 70
15 18 69
15 28 69
15 30 70
15 41 70
15 48 69
15 50 69
15 51 72
15 52 71
15 55 71
15 57 72
15 63 72
15 64 71
15 68 71
15 72 71
15 74 73
15 79 74
15 84 73
15 89 74
15 91 73
15 92 73
16 17 73
16 30 73
16 32 75
16 33 75
16 38 75
16 46 75
16 48 75
16 60 76
16 61 76
16 64 76
16 73 78
16 84 77
16 85 78
16 89 77
16 90 77
16 93 77
16 97 78
17 20 77
17 21 79
17 23 79
17 25 80
17 28 79
17 29 80
17 37 80
17 40 80
17 48 80
17 50 82
17 56 81
17 60 82
17 64 81
17 77 82
17 89 81
17 98 81
17 99 81
18 22 83
18 30 84
18 32 83
18 33 84
18 35 83
18 40 84
18 42 83
18 46 83
18 47 86
18 51 86
18 54 85
18 56 85
18 58 86
18 61 85
18 65 85
18 67 86
18 72 88
18 83 88
18 90 87
18 97 88
19 23 88
19 27 88
19 34 87
19 36 87
19 40 89
19 46 90
19 48 90
19 51 90
19 53 90
19 55 89
19 57 89
19 78 90
19 87 92
19 96 92
19 99 91
19 100 91
20 21 91
20 22 91
20 23 91
20 29 92
20 40 93
20 43 94
20 50 93
20 54 94
20 55 94
20 62 93
20 65 93
20 77 94
20 85 96
20 87 95
20 94 96
20 97 95
20 100 96
21 22 96
21 23 95
21 28 96
21 33 98
21 34 98
21 37 97
21 38 97
21 40 97
21 41 97
21 44 97
21 45 97
21 51 99
21 54 100
21 56 100
21 59 100
21 62 100
21 70 100
21 75 100
21 83 99
21 91 102
22 28 101
22 31 102
22 36 101
22 37 102
22 55 101
22 60 102
22 62 102
22 63 103
22 69 104
22 71 104
22 72 103
22 74 104
22 89 103
22 91 103
22 97 103
22 100 105
23 24 106
23 29 105
23 45 105
23 46 106
23 52 105
23 57 106
23 70 106
23 71 108
23 72 107
23 74 107
23 80 108
23 92 107
23 93 107
23 99 108
24 25 108
24 37 110
24 45 109
24 47 109
24 50 109
24 52 110
24 60 109
24 62 109
24 64 109
24 67 111
24 70 111
24 73 112
24 79 112
24 82 111
24 89 111
24 95 112
25 28 112
25 37 114
25 53 113
25 54 114
25 56 114
25 58 113
25 64 114
25 68 113
25 73 113
25 80 115
25 81 115
25 86 115
25 94 115
25 96 116
26 28 115
26 33 115
26 34 116
26 42 118
26 43 118
26 46 117
26 56 117
26 59 118
26 63 118
26 65 117
26 66 118
26 75 119
26 79 119
26 80 120
26 85 119
26 91 119
26 92 120
26 99 120
27 28 119
27 30 121
27 38 122
27 39 121
27 40 121
27 43 121
27 46 122
27 47 121
27 51 122
27 65 123
27 68 124
27 78 123
27 82 124
27 83 123
27 88 123
27 89 124
27 90 123
27 92 125
27 95 126
27 99 126
28 46 126
28 47 126
28 56 126
28 63 125
28 67 125
28 68 127
28 72 128
28 75 127
28 76 128
28 81 128
28 82 128
28 87 128
28 93 128
28 96 130
28 98 130
29 30 129
29 32 129
29 38 130
29 44 130
29 45 130
29 48 130
29 54 132
29 56 131
29 60 132
29 61 132
29 62 132
29 65 132
29 70 132
29 73 131
29 74 134
29 78 134
29 80 134
29 81 133
29 90 134
29 93 133
29 96 133
29 97 133
30 31 136
30 32 135
30 35 136
30 44 135
30 49 135
30 57 135
30 62 135
30 67 136
30 69 138
30 73 138
30 74 137
30 80 137
30 83 137
30 98 137
30 99 138
30 100 138
31 43 139
31 44 140
31 46 139
31 47 140
31 52 139
31 66 139
31 70 139
31 73 140
31 75 141
31 84 141
31 89 142
31 96 142
32 37 141
32 39 142
32 49 142
32 53 142
32 61 143
32 63 143
32 64 144
32 65 143
32 66 144
32 67 144
32 70 144
32 72 144
32 75 146
32 80 146
32 83 146
32 85 145
33 44 145
33 59 146
33 62 145
33 68 145
33 77 148
33 80 148
33 86 147
33 91 148
33 97 148
33 98 147
34 35 148
34 37 147
34 44 150
34 47 150
34 68 149
34 78 150
34 85 150
34 88 149
34 97 150
35 36 149
35 41 152
35 54 151
35 74 152
35 94 152
35 95 151
35 99 152
36 40 151
36 47 152
36 50 153
36 51 153
36 68 154
36 70 154
36 79 153
36 85 153
36 86 153
36 90 154
36 93 156
36 98 156
36 100 156
37 41 156
37 50 155
37 63 155
37 65 155
37 67 155
37 75 157
37 82 157
37 90 158
37 95 158
37 99 157
38 40 158
38 45 157
38 50 158
38 57 160
38 61 159
38 66 159
38 70 160
38 77 160
38 81 160
38 84 160
38 87 159
38 96 162
38 100 162
39 52 162
39 55 161
39 71 161
39 75 161
39 84 162
39 85 161
39 94 163
39 96 164
40 41 163
40 48 163
40 49 163
40 54 163
40 55 163
40 60 163
40 65 165
40 67 166
40 71 165
40 76 165
40 77 165
40 82 166
40 90 166
40 99 166
41 45 168
41 46 167
41 48 167
41 57 167
41 85 167
41 89 168
41 94 168
41 96 167
42 46 170
42 68 170
42 69 170
42 82 169
42 87 169
42 90 169
42 95 169
42 96 169
42 98 172
43 45 171
43 49 171
43 51 171
43 55 172
43 63 171
43 64 171
43 65 171
43 67 174
43 75 174
43 79 174
43 80 174
43 81 173
43 84 174
43 93 174
43 96 173
43 99 175
44 47 176
44 49 175
44 52 175
44 54 176
44 58 175
44 68 175
44 80 175
44 88 177
44 91 177
44 95 177
44 98 178
45 50 178
45 51 177
45 53 177
45 58 177
45 67 180
45 68 179
45 76 179
45 80 180
45 81 179
45 87 180
45 88 179
45 92 179
45 93 182
45 96 182
46 47 181
46 56 182
46 57 182
46 61 182
46 71 181
46 75 182
46 76 184
46 81 184
46 88 183
46 92 183
46 94 184
46 97 184
46 98 183
47 54 183
47 60 186
47 72 185
47 75 185
47 79 185
47 81 185
47 88 186
47 91 186
47 93 185
47 95 187
48 59 187
48 61 188
48 63 188
48 65 187
48 70 188
48 72 187
48 74 188
48 78 189
48 84 190
48 88 189
48 94 189
49 63 190
49 66 189
49 67 190
49 72 190
49 76 191
49 79 192
49 89 191
49 91 191
50 52 191
50 55 192
50 62 191
50 64 191
50 73 194
50 76 194
50 84 193
50 87 194
51 56 193
51 67 193
51 70 193
51 73 194
51 74 195
51 76 196
51 77 195
51 81 195
51 88 195
51 90 195
51 99 195
52 69 196
52 73 198
52 75 197
52 80 198
52 89 198
53 56 197
53 64 198
53 73 198
53 74 198
53 90 200
53 99 200
54 55 200
54 58 200
54 65 200
54 72 200
54 90 199
54 92 200
54 98 201
55 59 202
55 73 202
55 80 202
55 89 202
55 97 201
55 99 201
56 58 201
56 60 204
56 63 203
56 68 204
56 86 204
56 95 204
56 96 203
56 98 204
56 99 203
57 61 206
57 62 206
57 63 205
57 66 205
57 68 205
57 73 206
57 85 206
57 93 206
58 62 207
58 67 208
58 69 208
58 75 207
58 77 208
58 78 208
58 87 208
58 97 207
58 99 209
59 72 210
59 73 210
59 77 210
59 78 210
59 79 210
59 84 210
60 69 210
60 75 211
60 78 212
60 79 211
60 85 212
60 90 211
60 93 211
60 94 211
60 100 212
61 63 214
61 64 213
61 66 214
61 70 214
61 71 214
61 74 213
61 79 214
61 89 214
61 92 215
61 99 215
62 63 215
62 71 216
62 73 215
62 74 215
62 75 215
62 80 216
62 81 218
62 86 218
63 78 218
63 79 217
63 86 217
63 93 218
63 95 218
63 100 218
64 69 220
64 79 220
64 80 220
64 83 219
64 91 219
64 97 220
64 98 219
65 70 219
65 76 222
65 86 222
65 87 222
65 92 222
66 67 221
66 75 222
66 80 222
66 85 221
66 90 224
66 91 223
66 95 223
67 68 224
67 70 223
67 73 224
67 84 224
67 90 224
67 94 225
67 95 225
67 97 226
67 98 225
68 69 226
68 71 225
68 81 226
68 83 226
68 86 227
68 87 228
68 88 228
68 97 228
69 85 228
69 88 228
69 90 228
69 93 227
70 71 230
70 73 230
70 75 229
70 76 230
70 83 230
71 75 230
71 80 229
71 85 230
72 76 231
72 82 231
72 83 231
72 89 232
72 93 231
72 100 231
73 78 231
73 80 232
73 88 233
73 92 233
73 98 234
73 99 233
74 80 233
74 94 234
74 97 234
74 98 233
75 86 236
75 87 236
75 93 236
75 97 236
76 80 236
76 82 236
76 87 236
76 92 236
76 93 237
76 97 238
76 98 238
76 100 238
77 88 237
77 100 237
78 83 237
78 85 238
78 90 240
78 94 239
78 96 240
78 98 240
79 81 240
79 88 239
79 91 240
79 94 239
79 97 242
79 100 242
80 84 242
80 87 241
80 88 241
80 93 241
80 99 242
81 93 242
82 84 244
82 87 244
82 89 243
82 92 244
82 99 243
83 84 243
83 91 244
83 97 244
83 98 245
85 86 246
85 90 245
85 91 246
86 88 245
86 89 246
86 92 245
86 97 245
87 90 247
87 94 247
88 93 247
88 96 247
88 99 248
89 98 248
90 100 247
91 96 247
91 97 250
92 94 249
93 94 250
94 98 250
95 100 249
96 98 249
97 100 249
99 100 249

1

18 37
1 2 1
1 3 1
1 4 2
1 7 2
1 9 2
1 16 2
2 3 2
2 7 1
2 11 3
2 13 3
2 18 3
3 6 3
3 8 4
3 11 3
3 12 3
4 5 4
4 8 5
4 10 6
5 10 5
5 12 5
5 14 5
6 7 5
6 11 6
6 15 6
7 10 7
7 11 7
7 14 8
7 15 7
7 17 8
8 14 8
8 17 8
9 16 8
10 12 10
13 15 10
13 17 10
15 17 10
17 18 10

4

数据范围与约定

对于全部数据，1≤n≤100，1≤m≤1000，1≤c≤10^9。

数据保证不会出现自回边和重边。

注意：具有相同权值的边不会超过 10 条。