#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back typedef long long ll; using namespace std; const int maxn=1e5+10,mod=1e9+7; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,m; vector<pi>E[maxn]; int dis[maxn]; ll s1[maxn],s2[maxn],s3[maxn]; int vis[maxn]; void dij(){ up(i,1,n)dis[i]=2e9; dis[1]=0;priority_queue<pi>q; q.push(m_p(0,1)); s1[1]=1,s2[1]=s3[1]=0; while(!q.empty()){ int u=q.top().p2;q.pop(); if(vis[u])continue;vis[u]=1; for(auto it:E[u]){ int x=it.p1,w=it.p2; if(dis[x]>dis[u]+w){ dis[x]=dis[u]+w; s1[x]=s2[x]=s3[x]=0; q.push(m_p(-dis[x],x)); } if(dis[x]==dis[u]+w){ (s1[x]+=s1[u])%=mod; (s2[x]+=(s2[u]+s1[u])%mod)%=mod; (s3[x]+=((s3[u]+2*s2[u]%mod)%mod+s1[u])%mod)%=mod; } } } } void slv(){ n=read(),m=read(); up(i,1,m){ int x=read(),y=read(),w=read(); E[x].p_b(m_p(y,w)); }dij(); ll res=0; int IV2=(mod+1)/2; up(i,1,n)if(dis[i]<2e9)(res+=(s2[i]*1ll*s2[i]%mod-s3[i]+mod)%mod*1ll*IV2%mod)%=mod; cout<<res; } int main(){ //freopen("bob.in","r",stdin); //freopen("bob.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }