#include<bits/stdc++.h> using namespace std; #define int long long const int N=2e5+10,M=1e9+7,ny=5e8+4; int n,m,ans,dis[N],cnt[N],sum[N],pfh[N];bool vis[N]; struct Edge{int v,w,nx;}e[N];int CNT,h[N]; void add(int u,int v,int w){e[++CNT]={v,w,h[u]};h[u]=CNT;} priority_queue<pair<int,int> >q; void dij(){ dis[1]=0;q.push({0,1});cnt[1]=1; while(!q.empty()){ int u=q.top().second;q.pop(); if(vis[u])continue;vis[u]=1; int v,w; for(int i=h[u];i>0;i=e[i].nx){ v=e[i].v;w=e[i].w; if(dis[u]+w==dis[v]){ cnt[v]+=cnt[u];cnt[v]%=M; sum[v]+=(sum[u]+cnt[u])%M;sum[v]%=M; pfh[v]+=(pfh[u]+2*sum[u]%M+cnt[u])%M;pfh[v]%=M; } if(dis[u]+w<dis[v]){ cnt[v]=sum[v]=pfh[v]=0; cnt[v]+=cnt[u];cnt[v]%=M; sum[v]+=(sum[u]+cnt[u])%M;sum[v]%=M; pfh[v]+=(pfh[u]+2*sum[u]%M+cnt[u])%M;pfh[v]%=M; dis[v]=dis[u]+w; q.push({-dis[v],v}); } } } } signed main(){ memset(dis,0x3f,sizeof(dis)); scanf("%lld%lld",&n,&m); int u,v,w; for(int i=1;i<=m;i++){ scanf("%lld%lld%lld",&u,&v,&w); add(u,v,w); } dij(); for(int i=1;i<=n;i++){ // cout<<cnt[i]<<" "<<sum[i]<<" "<<pfh[i]<<endl; ans+=(sum[i]*sum[i]%M-pfh[i]+M)*ny%M; ans%=M; } printf("%lld\n",ans); return 0; }