#include<bits/stdc++.h> using namespace std; const int N = 1e5+10,md = 1e9+7; #define int long long int n,m,ans; vector<pair<int,int> > G[N]; struct T{ int dis; int vis; int num; int sum; int sum2; }a[N]; int qpow(int x,int y){ int tmp=1; while(y){ if(y&1) tmp=tmp%md*x%md; x=x%md*x%md; y=y>>1; } return tmp; } void Dijkstra(int x){ for(int i=1;i<=n;i++){ a[i].dis=1e9; a[i].vis=0; } priority_queue<pair<int,int> > pq; pq.push(make_pair(0,x)); a[x].dis=0; a[x].num=1; a[x].sum=0; a[x].sum2=0; a[x].vis=0; while(!pq.empty()){ int x=pq.top().second; pq.pop(); if(a[x].vis) continue; a[x].vis=1; for(int i=0;i<G[x].size();i++){ int v=G[x][i].first,w=G[x][i].second; if(a[v].dis>a[x].dis+w){ a[v].dis=a[x].dis+w; a[v].num=a[x].num; a[v].sum=(a[x].sum%md+a[x].num%md)%md; a[v].sum2=(a[x].sum2%md+2%md*a[x].sum%md+a[x].num%md)%md; pq.push(make_pair(-a[v].dis,v)); } else if(a[v].dis==a[x].dis+w){ a[v].num=(a[v].num%md+a[x].num%md)%md; a[v].sum=(a[v].sum%md+a[x].sum%md+a[x].num%md)%md; a[v].sum2=(a[v].sum2%md+a[x].sum2%md+2%md*a[x].sum%md+a[x].num%md)%md; } } } } signed main(){ cin>>n>>m; for(int i=1;i<=m;i++){ int x,y,w; cin>>x>>y>>w; G[x].push_back(make_pair(y,w)); } Dijkstra(1); for(int i=1;i<=n;i++){ ans=(ans%md+(a[i].sum%md*a[i].sum%md-a[i].sum2%md)*qpow(2,md-2)%md)%md; } /* for(int i=1;i<=n;i++){ cout<<a[i].dis<<" "<<a[i].num<<" "<<a[i].sum<<" "<<a[i].sum2<<endl; } */ cout<<ans%md<<endl; return 0; }