额。。。。。。。。

#include<bits/stdc++.h>
using namespace std;
int n,m,fire[1006],mnm=0,team[1006],inf=0x7ffffff,book[1006],key[1006],h=1,al=2<<31-1;
struct node
{
	int to,value,next;
}edge[500006];
void add(int v,int u,int value)
{
	mnm++;
	edge[mnm].next=fire[v];
	edge[mnm].value=value;
	edge[mnm].to=u;
	fire[v]=mnm;
}
void find(int w,int g,int v)
{
	for(int i=fire[w];i;i=edge[i].next)
	  {
	  	 if(edge[i].value+v>team[g]) continue;
		 if(edge[i].to==g) 
		   {
		   	key[g]++;
		   	continue;
		   }
		 v+=edge[i].value;
		 find(edge[i].to,g,v); 
	  }
	return ;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++) 
	  {
	  	int x,y,va;
	  	cin>>x>>y>>va;
	  	add(x,y,va);
	  	add(y,x,va);
	  }
   for(int i=1;i<=n;i++)
       {
       	 key[i]=1;
       	 team[i]=inf;
       }
   for(int i=fire[1];i;i=edge[i].next)
      {
      	int v=edge[i].to;
      	team[v]=min(team[v],edge[i].value);
      }
   book[1]=1;
    int ans=1;
   while(ans!=n-1)
      {
      	int minn=inf,k=0;
      	for(int i=1;i<=n;i++)
      	  {
      	  	 if(book[i]) continue;
      	  	 if(team[i]<minn) 
      	  	   {
      	  	   	 minn=team[i];
      	  	   	 k=i;
      	  	   }
      	  }
      	 book[k]=1;
        ans++;
        for(int i=fire[k];i;i=edge[i].next)
          {
         	int v=edge[i].to;
         	if(book[v]) continue;
         	if(team[k]+edge[i].value<team[v])
            team[v]=team[k]+edge[i].value;
         }
      }
   for(int i=1;i<=n;i++)
     find(1,i,0);
   for(int i=2;i<=n;i++)
     h=(h*(key[i]-1))%al;
   cout<<h;
   return 0;
}