#include<bits/stdc++.h> #define PIII pair<pair<int,int>,int> using namespace std; int n,m; const int mod=1e9+7; const int N=2e5; int head[N],nxt[N],to[N],w[N],idx=0; int dis[100010]; int vis[100010]; vector<int> sta[20]; int f[100010]; priority_queue<PIII,vector<PIII>,greater<PIII> >q; void add(int x,int y,int v){ to[++idx]=y; w[idx]=v; nxt[idx]=head[x]; head[x]=idx; } int d[100010]; int main(){ cin>>n>>m; int ppp=0; for(int i=1;i<=m;i++){ int u,v,x; cin>>u>>v>>x; add(u,v,x); if(x!=1) ppp=1; } if(ppp==1||n<=10){ memset(dis,0x3f,sizeof dis); dis[1]=0; q.push({{0,0},1}); while(!q.empty()){ PIII u=q.top(); q.pop(); //cout<<u.second<<":"; if(vis[u.second]){ //cout<<u.second<<" "<<u.first.first<<" "<<f[u.second]<<endl; if(u.first.first!=f[u.second]) continue; } vis[u.second]=1; f[u.second]=u.first.first; sta[u.second].push_back(u.first.second); for(int i=head[u.second];i;i=nxt[i]){ int v=to[i]; //cout<<v<<" "; if(w[i]+f[u.second]<=dis[v]){ //cout<<v<<" "; dis[v]=w[i]+f[u.second]; q.push({{dis[v],u.first.second+1},v}); } } //cout<<endl; } //cout<<endl; long long ans=0; for(int i=1;i<=n;i++){ //cout<<sta[i].size()<<endl; for(int j=0;j<sta[i].size();j++){ for(int k=j+1;k<sta[i].size();k++){ ans+=sta[i][j]*sta[i][k]%mod; ans%=mod; } } } cout<<ans<<endl; } else{ memset(dis,0x3f,sizeof dis); dis[1]=0; //priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > qq; q.push({{0,1},1});//t,u,geshu while(!q.empty()){ PIII u=q.top(); q.pop(); if(vis[u.first.second]){ if(f[u.first.second]==u.first.first) d[u.first.second]+=u.second; continue; } vis[u.first.second]=1; f[u.first.second]=u.first.first; d[u.first.second]+=u.second; for(int i=head[u.first.second];i;i=nxt[i]){ int v=to[i]; if(dis[v]>=u.first.first+1){ dis[v]=u.first.first+1; q.push({{dis[v],v},d[u.first.second]}); } } } long long ans=0; for(int i=1;i<=n;i++){ ans+=f[i]*f[i]%mod*(d[i]*(d[i]-1)/2)%mod; ans%=mod; } cout<<ans<<endl; } return 0; }