#include <iostream>
#include <fstream>
#include <cmath>
#define nrn 1501
#define nrm 2501
#define maxi 999999999
#define mod 104659
#define mini 0.000001
using namespace std;
ifstream f("dmin.in");
ofstream g("dmin.out");
int t[3][2*nrm], viz[nrn], cost[nrn], c[nrm*2], start[nrn],n,m,i,cnt[nrn];
void liste_adiacenta()
{
    int i,x,y,z,k=0;
    for (i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        t[0][++k]=y; t[1][k]=start[x]; start[x]=k;
        t[2][k]=z;
    }
}
void ford(int inc)
{
    int i,x,k,pi=1,ps=1;
    for (i=1;i<=n;i++)
        cost[i]=maxi;
    cost[inc]=0; c[pi]=inc; cnt[inc]=1;
    while (ps<=pi)
    {
        k=c[ps];
        viz[k]=0;
        x=start[k];
        while (x)
        {
            if (cost[t[0][x]]-(cost[k]+t[2][x])>mini)
            {
                cost[t[0][x]]=cost[k]+t[2][x];
                cnt[t[0][x]]=0;
                if (!viz[t[0][x]])
                    viz[t[0][x]]=1 , c[++pi]=t[0][x];
            }
            if (abs(cost[t[0][x]]-(cost[k]+t[2][x]))<mini)
                cnt[t[0][x]]=cnt[t[0][x]]+cnt[k]%mod;
            x=t[1][x];
        }
        ps++;
    }
}
int main()
{
    f>>n>>m;
    liste_adiacenta();
    ford(1);
    for (i=2;i<=n;i++)
        g<<cnt[i]<<" ";
    return 0;
}