#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 105, M = 1005, P = 31011;
int fa[N], siz[N], id[N];
ll t[N][N], g[N][N];
vector<int> node;
struct Edge {
	int u, v, w;
}e[M];
vector<Edge> edge;
bool cmp(Edge x, Edge y) {
	return x.w < y.w;
}
int getfa(int x) {
	if(fa[x] == x) {
		return x;
	}
	return fa[x] = getfa(fa[x]);
}
void merge(int x, int y) {
	int fx = getfa(x), fy = getfa(y);
	if(fx == fy) return;
	if(siz[fx] < siz[fy]) swap(fx, fy);
	siz[fx] += siz[fy];
	fa[fy] = fx;
}
bool Kruscal(int n, int m) {
	int cnt = 0;
	for(int i = 1; i <= m; i++) {
		if(getfa(e[i].u) != getfa(e[i].v)) {
			merge(e[i].u, e[i].v);
			edge.push_back(e[i]);
			cnt++;
		}
		if(cnt >= n - 1) {
			return 1;
		}
	}
	if(cnt < n - 1) {
		return 0;
	}
}
ll gauss(int n) {
	int v = 1;
	for(int i = 1; i <= n; i++) {
		if(!g[i][i]) {
			for(int j = i + 1; j <= n; j++) {
				if(g[j][i]) {
					swap(g[i], g[j]);
					v *= -1;
				}
			}
		}
		for(int j = i + 1; j <= n; j++) {
			while(g[i][i]) {
				int q = g[j][i] / g[i][i];
				for(int k = i; k <= n; k++) {
					g[j][k] -= g[i][k] * q % P;
					g[j][k] = (g[j][k] + P) % P;
				}
				swap(g[i], g[j]);
				v *= -1;
			}
			swap(g[i], g[j]);
			v *= -1;
		}
	}
	ll res = (v + P) % P;
	for(int i = 1; i <= n; i++) {
		res = (res * g[i][i] + P) % P;
	}
	return res;
}
int main() {
//	freopen("data.txt", "r", stdin);
//	freopen("test.out", "w", stdout);
	int n, m;
	cin >> n >> m;
	for(int i = 0; i <= n; i++) {
		fa[i] = i;
		siz[i] = 1;
	}
	for(int i = 1; i <= m; i++) {
		cin >> e[i].u >> e[i].v >> e[i].w;
	}
	sort(e + 1, e + m + 1, cmp);
	int maxw = 1;
	e[1].w = 1;
	for(int i = 2; i <= m; i++) {
		if(e[i].w > e[i - 1].w) {
			e[i].w = ++maxw;
		}
	}
	for(int i = 1; i <= m; i++) {
		t[e[i].u][e[i].v] = t[e[i].v][e[i].u] = e[i].w;
	}
//	for(int i = 1; i <= n; i++) {
//		for(int j = 1; j <= n; j++) {
//			cout << t[i][j] << " ";
//		}
//		cout << endl;
//	}
	if(!Kruscal(n, m)) {
		cout << 0;
		return 0;
	}
	ll ans = 1;
	for(int l = 0; l < edge.size(); l++) {
		if(l && edge[l].w == edge[l - 1].w) continue;
		int k = edge[l].w;
		node.clear();
		memset(g, 0, sizeof(g));
		for(int i = 0; i <= n; i++) {
			fa[i] = i;
			siz[i] = 1;
		}
		for(int i = 0; i < edge.size(); i++) {
			if(edge[i].w != k) {
				merge(edge[i].u, edge[i].v);
			}
		}
		for(int i = 1; i <= n; i++) {
			int flag = 1;
			int fi = getfa(i);
			for(int j = 0; j < node.size(); j++) {
				if(fi == node[j]) {
					flag = 0;
					break;
				}
			}
			if(flag) {
				node.push_back(fi);
				id[fi] = node.size() - 1;
			}
		}
		for(int i = 1; i <= m; i++) {
			if(e[i].w == k) {
				int x = e[i].u, y = e[i].v;
				x = getfa(x), y = getfa(y);
				x = id[x], y = id[y];
				g[x][y]--, g[y][x]--;
				g[x][x]++, g[y][y]++;
			}
		}
//		for(int i = 0; i < node.size(); i++) {
//			for(int j = 0; j < node.size(); j++) {
//				cout << g[i][j] << " ";
//			}
//			cout << endl;
//		}
		ans = ans * gauss(node.size() - 1) % P;
//		for(int i = 0; i < node.size(); i++) {
//			cout << node[i] << " ";
//		}
//		cout << endl;
//		for(int i = 0; i < edge.size(); i++) {
//			cout << edge[i].u << " " << edge[i].v << endl;
//		}
	}
	cout << ans;
 	return 0;
}