题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1016
做这道题之前需要知道一些结论，同一个图的最小生成树中相同权值的边的个数是不会变的，如果有一种方案中权值为666的边有233条，那么另一种方案一定也是这样，并且它们在图中对连通性的影响也是相同的。
于是我们先求出一种方案，记录下每种权值的边对应的数量。然后把权值相同的边分为一组，对于每一组搜索选出边的合法方案，乘法原理一下答案就出来了。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mod=;
int inline readint(){
int Num;char ch;
while((ch=getchar())<''||ch>'');Num=ch-'';
while((ch=getchar())>=''&&ch<='') Num=Num*+ch-'';
return Num;
}
int n,m;
struct EDGE{
int u,v,w;
}e[],a[];
int cnt=,tot=;
bool cmp(EDGE a,EDGE b){
return a.w<b.w;
}
int fa[];
int getfa(int x){
return fa[x]==x?x:getfa(fa[x]);
}
int sum=;
void dfs(int x,int pos,int k){
if(pos==a[x].v+){
if(k==a[x].w) sum++;
return;
}
int fu=getfa(e[pos].u),
fv=getfa(e[pos].v);
if(fu!=fv){
fa[fu]=fv;
dfs(x,pos+,k+);
fa[fu]=fu;
fa[fv]=fv;
}
dfs(x,pos+,k);
}
int main(){
n=readint();
m=readint();
for(int i=;i<=m;i++){
e[i].u=readint();
e[i].v=readint();
e[i].w=readint();
}
sort(e+,e++m,cmp);
for(int i=;i<=n;i++) fa[i]=i;
for(int i=;i<=m;i++){
if(e[i].w!=e[i-].w){
a[cnt].v=i-;
a[++cnt].u=i;
}
int fu=getfa(e[i].u),
fv=getfa(e[i].v);
if(fu!=fv){
fa[fu]=fv;
a[cnt].w++;
tot++;
}
}
a[cnt].v=m;
if(tot!=n-){
puts("");
return ;
}
for(int i=;i<=n;i++) fa[i]=i;
int ans=;
for(int i=;i<=cnt;i++){
sum=;
dfs(i,a[i].u,);
ans=ans*sum%mod;
for(int j=a[i].u;j<=a[i].v;j++){
int fu=getfa(e[j].u),
fv=getfa(e[j].v);
if(fu!=fv) fa[fu]=fv;
}
}
printf("%d\n",ans);
return ;
}