#include<bits/stdc++.h> #define int long long using namespace std; const int maxn=2e5+7; const int INF=1e12; const int mod=1e9+7; const int Inv2=mod+1>>1; struct Edge{ int v,w; Edge(int _v=0,int _w=0){v=_v,w=_w;} };vector<Edge> E[maxn]; struct Node{ int x,Dis; Node(int _x=0,int _d=0){x=_x,Dis=_d;} }; inline bool operator<(const Node &A,const Node &B){return A.Dis<B.Dis;} inline bool operator>(const Node &A,const Node &B){return A.Dis>B.Dis;} int n,m; int c0[maxn]; int c1[maxn]; int c2[maxn]; int dis[maxn]; bool vis[maxn]; inline void Dij(){ priority_queue<Node,vector<Node>,greater<Node> >q; for(int i=1;i<=n;i++)dis[i]=INF,vis[i]=0; dis[1]=0; c0[1]=1; q.push(Node(1,0)); while(!q.empty()){ Node N=q.top();q.pop(); int u=N.x; // cout<<u<<endl; if(vis[u])continue; vis[u]=1; for(auto e:E[u]){ int v=e.v,w=e.w; if(dis[u]+w<dis[v]){ dis[v]=dis[u]+w; c0[v]=c0[u]; c1[v]=(c1[u]+c0[u])%mod; c2[v]=(c2[u]+2*c1[u]%mod+c0[u])%mod; q.push(Node(v,dis[v])); } else if(dis[u]+w==dis[v]){ dis[v]=dis[u]+w; (c0[v]+=c0[u])%=mod; (c1[v]+=(c1[u]+c0[u])%mod)%=mod; (c2[v]+=(c2[u]+2*c1[u]%mod+c0[u])%mod)%=mod; q.push(Node(v,dis[v])); } } } } signed main(){ #ifndef ONLINE_JUDGE freopen("bob.in","r",stdin); freopen("bob.out","w",stdout); #endif cin>>n>>m; for(int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; E[u].push_back(Edge(v,w)); } Dij(); int ret=0; for(int i=1;i<=n;i++){ int cur=(c1[i]*c1[i]%mod+mod-c2[i])%mod*Inv2%mod; (ret+=cur)%=mod; } cout<<ret<<endl; }