#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#define ll long long

using namespace std;

const int N=,M=,mod=1e9+;

int n,m,head[N],pre[N],dis[N],xnt,rd[N];

ll d1[N],d2[N],ans[M];

bool in[N];

queue<int> r;

struct Edge{

    int next,from,to,w;

    Edge(int n=,int f=,int t=,int w=):next(n),from(f),to(t),w(w) {}

}edge[M];

void spfa(int cur)

{

    memset(dis,,sizeof dis);

    queue<int> q;

    dis[cur]=;q.push(cur);in[cur]=;rd[cur]=;//

    while(q.size())

    {

        int k=q.front();q.pop();in[k]=;

        for(int i=head[k],v;i;i=edge[i].next)

        {

            if(dis[k]+edge[i].w==dis[v=edge[i].to])rd[v]++;

            if(dis[k]+edge[i].w<dis[v=edge[i].to])

            {

                rd[v]=;

                dis[v]=dis[k]+edge[i].w;

                if(!in[v])q.push(v),in[v]=;

            }

        }

    }

}

void dp(int cur)

{

    d2[cur]=;

    for(int i=head[cur],v;i;i=edge[i].next)

        if(dis[v=edge[i].to]==dis[cur]+edge[i].w)

        {

            if(!d2[v=edge[i].to])dp(v);

            (d2[cur]+=d2[v])%=mod;

        }

}

void tp(int cur)

{

    r.push(cur);

    for(int i=head[cur],v;i;i=edge[i].next)

        if(dis[v=edge[i].to]==dis[cur]+edge[i].w)//

        {

            rd[v=edge[i].to]--;

            if(!rd[v])tp(v);

        }

}

void solve(int cur)

{

//    printf("cur=%d\n",cur);

    memset(d1,,sizeof d1);

    memset(d2,,sizeof d2);

    while(r.size())r.pop();

    spfa(cur);

    tp(cur);

    dp(cur);

    d1[cur]=;

    while(r.size())

    {

        int k=r.front();r.pop();

        for(int i=head[k],v;i;i=edge[i].next)

            if(dis[v=edge[i].to]==dis[k]+edge[i].w)

                (d1[v]+=d1[k])%=mod;

    }

    for(int i=,u,v;i<=m;i++)

        if(dis[u=edge[i].from]+edge[i].w==dis[v=edge[i].to])//

        {

            (ans[i]+=d1[u]*d2[v])%=mod;

//            printf("from=%d to=%d t=%lld ans=%lld\n",edge[i].from,edge[i].to,d2[edge[i].to],ans[i]);

        }

}

int main()

{

    scanf("%d%d",&n,&m);int x,y,z;

    for(int i=;i<=m;i++)

    {

        scanf("%d%d%d",&x,&y,&z);

        edge[++xnt]=Edge(head[x],x,y,z);head[x]=xnt;

    }

    for(int i=;i<=n;i++)

        solve(i);

    for(int i=;i<=m;i++)

        printf("%lld\n",ans[i]);

    return ;

}