#include<bits/stdc++.h> #define int __int128 #define PIIII pair<pair<int,int>,pair<int,int> > using namespace std; const int M=3e5+10; const int mod=1e9+7; long long n,m; int dis[200010],d[200010],vis[200010],f[200010],sum1[200010],sum2[200010]; int head[M],nxt[M],to[M],w[M],idx; priority_queue<PIIII,vector<PIIII>,greater<PIIII> > q; void add(int x,int y,int v){ to[++idx]=y; w[idx]=v; nxt[idx]=head[x]; head[x]=idx; } signed main(){ cin>>n>>m; for(int i=1;i<=m;i++){ long long x,y,v; cin>>x>>y>>v; add(x,y,v); } memset(dis,0x5f,sizeof dis); memset(d,0,sizeof d); memset(sum1,0,sizeof sum1); memset(sum2,0,sizeof sum2); dis[1]=0; d[1]=1; q.push({{0,1},{0,0}});//费用，当前节点，从哪里转移，经过边数 //int k=1; while(!q.empty()){ PIIII u=q.top(); //k++; //if(k>100) break; q.pop(); if(vis[u.first.second]){ if(u.first.first==f[u.first.second]){ d[u.first.second]+=d[u.second.first]%mod; sum1[u.first.second]+=d[u.second.first]*u.second.second%mod; sum2[u.first.second]+=d[u.second.first]*u.second.second%mod*u.second.second%mod; d[u.first.second]%=mod; sum1[u.first.second]%=mod; sum2[u.first.second]%=mod; } continue; } vis[u.first.second]=1; f[u.first.second]=u.first.first; d[u.first.second]+=d[u.second.first]%mod; sum1[u.first.second]+=d[u.second.first]*u.second.second%mod; sum2[u.first.second]+=d[u.second.first]*u.second.second%mod*u.second.second%mod; d[u.first.second]%=mod; sum1[u.first.second]%=mod; sum2[u.first.second]%=mod; for(int i=head[u.first.second];i;i=nxt[i]){ //k++; //if(k>100) break; //cout<<to[i]<<" "<<i<<":"; int v=to[i]; if(dis[v]>=u.first.first+w[i]){ dis[v]=u.first.first+w[i]; q.push({{dis[v],v},{u.first.second,u.second.second+1}}); } } } long long ans=0; for(int i=1;i<=n;i++){ //cout<<sum1[i]<<" "<<sum2[i]<<endl; ans+=(sum1[i]*sum1[i]%mod-sum2[i])*500000004%mod; //cout<<ans<<endl; ans=(ans+mod)%mod; } cout<<ans<<endl; }