#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <bitset>
#include <cstring>
#include <cstdlib>

#define mp make_pair
#define pb push_back
#define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
#define PII pair<int,int>

#define Nmax 1505
#define MOD 104659
#define DIM 666013
#define INF 0x3f3f3f3f

using namespace std;
vector<PII> G[Nmax];
vector<int> daddy[Nmax];
queue<int> Q;
bitset<Nmax> inQ;

char buff[DIM];
int poz = DIM - 1;

int N,M;
long long dist[Nmax]; /// dist[k] distanta de la 1 la K
long long DP[Nmax]; /// DP[k] nr de drumuri care se termina in K

void Scanf(int &A){
    A = 0;
    while(buff[poz] < '0' || '9' < buff[poz])
        if( ++poz == DIM )fread(buff,1,DIM,stdin),poz = 0;
    while('0' <= buff[poz] && buff[poz] <= '9'){
        A = A * 10 + buff[poz] - 48;
        if( ++poz == DIM )fread(buff,1,DIM,stdin),poz = 0;
    }
}

void read()
{
    Scanf(N),Scanf(M);
    int a,b,c;
    FOR(i,1,M){
        Scanf(a);Scanf(b);Scanf(c);
        G[a].pb(mp(c,b));
        G[b].pb(mp(c,a));
    }
}

void bellman(int nodc)
{
    memset(dist,INF,sizeof(dist));
    dist[nodc] = 0;
    Q.push(nodc);
    while(!Q.empty()){
        nodc = Q.front();Q.pop();inQ[nodc] = 0;
        for(vector<PII>::iterator it = G[nodc].begin(); it != G[nodc].end(); ++it)
            if(dist[it->second] >= dist[nodc] + it->first)
            {
                if(dist[it->second] > dist[nodc] + it->first)
                {
                    dist[it->second] = dist[nodc] + it->first;
                    daddy[it->second].clear();
                    daddy[it->second].pb(nodc);
                    Q.push(it->second);
                    continue;
                }
                daddy[it->second].pb(nodc);
            }
    }
}

void prepare()
{
    for(int i = 1; i <= N; ++i)
    {
        vector<int>::iterator it = unique(daddy[i].begin(),daddy[i].end());
        daddy[i].resize(distance(daddy[i].begin(),it));
    }
}

int dynamic(int k)
{
    if(DP[k]) return DP[k];
    int sum = 0;
    for(vector<int>::iterator it= daddy[k].begin(); it != daddy[k].end(); ++it)
        sum = (sum + dynamic(*it)) % MOD;
    DP[k] = sum;
    return DP[k];
}

void solve()
{
    DP[1] = 1;
    for(int i = 2; i <= N; ++i)
        printf("%d ",dynamic(i));
}

int main()
{
    freopen("dmin.in","r",stdin);
    freopen("dmin.out","w",stdout);

    read();
    bellman(1);
    prepare();
    solve();

    return 0;
}