#include<bits/stdc++.h> #define int long long using namespace std; int n,m; vector<pair<int,int>>e[100005]; int dis[100005],cnt[100005],sum[100005],sqrsum[100005]; bool vis[100005]; void dij(){ priority_queue<pair<int,int>>q; q.push({0,1}); for(int i=1;i<=n;i++)dis[i]=2e9,cnt[i]=0,vis[i]=0; dis[1]=sum[1]=sqrsum[1]=0,cnt[1]=1; while(q.size()){ int p=q.top().second; q.pop(); if(vis[p])continue; vis[p]=1; for(auto x:e[p]){ if(dis[x.first]>dis[p]+x.second){ dis[x.first]=dis[p]+x.second; cnt[x.first]=cnt[p]; sum[x.first]=sum[p]+cnt[p]; sqrsum[x.first]=sqrsum[p]+sum[p]+sum[p]+cnt[p]; q.push({-dis[x.first],x.first}); } else if(dis[x.first]==dis[p]+x.second){ cnt[x.first]=cnt[p]; sum[x.first]=sum[p]+cnt[p]; sqrsum[x.first]=sqrsum[p]+sum[p]+sum[p]+cnt[p]; } } } } const int mod=1e9+7; const int inv2=(mod+1)/2; signed main(){ cin>>n>>m; for(int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; e[u].push_back({v,w}); } dij(); // for(int i=1;i<=n;i++)cout<<dis[i]<<" "; int ans=0; for(int i=1;i<=n;i++){ // cout<<cnt[i]<<" "<<sum[i]<<" "<<sqrsum[i]<<endl; ans+=((sum[i]*sum[i]-sqrsum[i])%mod*inv2%mod+mod); ans%=mod; } cout<<ans<<endl; return 0; }