#include<bits/stdc++.h> #define int long long #define PIIII pair<pair<int,int>,pair<int,int> > using namespace std; const int M=2e5+10; const int mod=1e9+7; int n,m,dis[100010],d[100010],vis[100010],f[100010],sum1[100010],sum2[100010]; 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; //cout<<n<<" "<<m<<endl; for(int i=1;i<=m;i++){ int x,y,v; cin>>x>>y>>v; //cout<<i<<" "<<x<<" "<<y<<" "<<v<<endl; add(x,y,v); } //cout<<endl; //cout<<"$$$"; memset(dis,0x3f,sizeof dis); //cout<<"@@@"; dis[1]=0; d[1]=1; //cout<<"???"; q.push({{0,1},{0,0}});//费用，当前节点，从哪里转移，经过边数 //cout<<"!!!"; int k=1; //for(int i=head[1];i;i=nxt[i]) cout<<to[i]<<":"<<i<<" "; // cout<<endl; while(!q.empty()){ //cout<<k<<" "; PIIII u=q.top(); //cout<<u.first.second<<" "; 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; }