#include<bits/stdc++.h> #define int long long using namespace std; const int mod=1e9+7; priority_queue<pair<int,pair<int,int> > >pq; int n,m; int head[200010],nxt[200010],len=0,e[200010],cost[200010]; void textread(){ freopen("test.in","r",stdin); freopen("test.out","w",stdout); } void textread2(){ freopen("bob.in","r",stdin); freopen("bob.out","w",stdout); } void add_edge(int x,int y,int z){ len++; e[len]=y; cost[len]=z; nxt[len]=head[x]; head[x]=len; } int sum[200010],dis[200010],ans[200010]; bool flag[200010]; void dij(){ dis[1]=0; sum[1]=0; ans[1]=0; pq.push(make_pair(0,make_pair(0,1))); int num=0; while(!pq.empty()){ int d=-pq.top().first,u=pq.top().second.second,edg=pq.top().second.first; pq.pop(); flag[u]=1; for(int i=head[u];i!=-1&&i!=0;i=nxt[i]){ int v=e[i],w=cost[i]; if(flag[v])continue; if(dis[v]>d+w){ sum[v]=edg+1; dis[v]=d+w; ans[v]=0; pq.push(make_pair(-dis[v],make_pair(edg+1,v))); }else if(dis[v]==d+w){ ans[v]+=sum[v]*(edg+1); ans[i]%=mod; sum[v]+=edg+1; sum[i]%=mod; pq.push(make_pair(-dis[v],make_pair(edg+1,v))); } } } } void init(){ memset(head,-1,sizeof(head)); memset(sum,0,sizeof(sum)); memset(dis,0x3f,sizeof(dis)); memset(ans,0,sizeof(ans)); while(!pq.empty())pq.pop(); } signed main(){ ios::sync_with_stdio(0); //textread2(); init(); cin>>n>>m; for(int i=1;i<=m;i++){ int x,y,z; cin>>x>>y>>z; add_edge(x,y,z); } dij(); int res=0; for(int i=1;i<=n;i++){ if(dis[i]<=100000000){ res+=ans[i]; } } cout<<res; return 0; }