using namespace std; const int N = 110, M = 1010, mod = 31011;
struct Edge {
int x, y, w;
} e[M];
bool cmp(Edge a, Edge b) {
return a.w < b.w;
} int f[N], n, m;
int find(int x) {
return f[x] == x ? x : find(f[x]); //注意这里没有路径压缩
}
struct sEdge {
int l, r, w;
} se[1010];
int dfs(int x, int now, int k) {
if (now == se[x].r + 1)
return k == se[x].w;
int sum = 0;
int fx = find(e[now].x), fy = find(e[now].y);
if (fx != fy) {
f[fx] = fy;
sum += dfs(x, now + 1, k + 1);
f[fx] = fx, f[fy] = fy; // 把 find 中 路径压缩放置这里
}
return sum + dfs(x, now + 1, k);
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i)
f[i] = i;
for (int i = 1; i <= m; ++i)
cin >> e[i].x >> e[i].y >> e[i].w;
sort(e + 1, e + m + 1, cmp);
int num = 1, snum = 0;
for (int i = 1; i <= m; i++) {
if (e[i].w != e[i - 1].w)
se[snum++].r = i - 1, se[snum].l = i;
int fx = find(e[i].x), fy = find(e[i].y);
if (fx != fy)
f[fx] = fy, se[snum].w++, num++;
}
if (num < n) {
cout << 0;
return 0;
}
se[snum].r = m;
for (int i = 1; i <= n; ++i)
f[i] = i;
int ans = 1;
for (int i = 1; i <= snum; ++i) {
ans = ans * dfs(i, se[i].l, 0) % mod;
for (int j = se[i].l; j <= se[i].r; ++j) {
int fx = find(e[j].x), fy = find(e[j].y);
if (fx != fy)
f[fx] = fy;
}
}
cout << ans;
return 0;
}