#include<bits/stdc++.h> #define int long long using namespace std; int n,m; vector<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(int x:e[p]){ if(dis[x]>dis[p]+1){ dis[x]=dis[p]+1; cnt[x]=cnt[p]; sum[x]=sum[p]+cnt[p]; sqrsum[x]=sqrsum[p]+sum[p]+sum[p]+cnt[p]; q.push({-dis[x],x}); } else if(dis[x]==dis[p]+1){ cnt[x]=cnt[p]; sum[x]=sum[p]+cnt[p]; sqrsum[x]=sqrsum[p]+sum[p]+sum[p]+cnt[p]; } } } } const int mod=1e9+7; 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); } dij(); int sqr=0,sm=0; for(int i=1;i<=n;i++){ sqr+=sqrsum[i]; sm+=sum[i]; sqr%=mod; sm%=mod; } cout<<((sm*sm-sqr)%mod+mod)%mod<<endl; return 0; }