Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 110

#define MAXM 1010

#define MOD 31011

struct edge

{

	int u,v,w;

}e[MAXM];

bool cmp(edge a,edge b){return a.w < b.w;}

struct block

{

	int l,r,v;

}b[MAXM];

int cnt = 0;

int f[MAXN];

int find(int x){return (x == f[x] ? x : find(f[x]));}

int scc[MAXN];

int ins(int x){return (x == scc[x] ? x : scc[x] = ins(scc[x]));}

int g[MAXN][MAXN];

int matrixtree(int n)

{

	int res = 1,tag = 1;

	--n;

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= n;++j)

		{

			g[i][j] = (g[i][j] % MOD + MOD) % MOD;

		}

	}

	for(int i = 1;i <= n;++i)

	{

		for(int j = i + 1;j <= n;++j)

		{

			int a = g[i][i],b = g[j][i];

			while(b)

			{

				int div = a / b;

				for(int k = i;k <= n;++k)

				{

					g[i][k] = (g[i][k] - g[j][k] * div % MOD + MOD) % MOD;

					swap(g[i][k],g[j][k]);

				}

				a = a % b;swap(a,b);tag = -tag;

			}

		}

		res = res * g[i][i] % MOD;

	}

	if(tag == -1)res = (MOD - res) % MOD;

	return res;

}

int v[MAXN][MAXN];

bool vis[MAXN];

int to[MAXN],tot = 0;

int tr[MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)

	{

		f[i] = i;

		scc[i] = i;

	}

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);

	}

	sort(e + 1,e + 1 + m,cmp);

	for(int i = 1;i <= m;++i)

	{

		if(e[i].w != e[i - 1].w)

		{

			b[++cnt].l = i;

			b[cnt - 1].r = i - 1;

			b[cnt].v = e[i].w;

		}

	}

	b[cnt].r = m;

	long long ans = 1;

	for(int i = 1;i <= cnt;++i)

	{

		for(int j = b[i].l;j <= b[i].r;++j)

		{

			register int p = ins(e[j].u),q = ins(e[j].v);

			if(p != q)

			{

				scc[p] = q;

			}

		}

		for(int j = 1;j <= n;++j)

		{

			v[j][0] = 0;

		}

		memset(vis,0,sizeof(vis));

		memset(to,0,sizeof(to));

		for(int j = b[i].l;j <= b[i].r;++j)

		{

			if(find(e[j].u) == find(e[j].v))continue;

			if(vis[ins(e[j].u)])

			{

				v[to[ins(e[j].u)]][++v[to[ins(e[j].u)]][0]] = j;

			}

			else

			{

				vis[ins(e[j].u)] = true;

				to[ins(e[j].u)] = ++tot;

				v[tot][++v[tot][0]] = j;

			}

		}

		for(int k = 1;k <= tot;++k)

		{

			memset(g,0,sizeof(g));

			memset(tr,0,sizeof(tr));

			int vcnt = 0;

			for(int p = 1;p <= v[k][0];++p)

			{

				if(tr[find(e[v[k][p]].u)] == 0)tr[find(e[v[k][p]].u)] = ++vcnt;

				if(tr[find(e[v[k][p]].v)] == 0)tr[find(e[v[k][p]].v)] = ++vcnt;

				g[tr[find(e[v[k][p]].u)]][tr[find(e[v[k][p]].u)]] += 1;g[tr[find(e[v[k][p]].v)]][tr[find(e[v[k][p]].v)]] += 1;

				g[tr[find(e[v[k][p]].u)]][tr[find(e[v[k][p]].v)]] -= 1;g[tr[find(e[v[k][p]].v)]][tr[find(e[v[k][p]].u)]] -= 1;

			}

			ans = ans * matrixtree(vcnt) % MOD;

		}

		for(int i = 1;i <= n;++i)

		{

			f[i] = scc[i];

		}

	}

	int root = ins(1);

	for(int i = 1;i <= n;++i)

	{

		if(ins(i) != root)

		{

			cout << 0 << endl;

			return 0;

		}

	}

	cout << ans << endl;

	return 0;

}