#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <bits/stdc++.h>
using namespace std;

#define MAXN 1001
#define INF numeric_limits < int > ::max() - 100
#define pb push_back
#define mp make_pair
#define MOD 104659

ifstream f("dmin.in");
ofstream g("dmin.out");

long long n , m , st , fn , x ,y ,z ,i ,j ;
vector < pair < long long , long long > > G[MAXN];
long long d[MAXN], val[MAXN][MAXN];
bool uz[MAXN];
long long drum[MAXN];
queue < long long > q;



int main()
{
    f >> n >> m ;
    for ( ; m-- ; )
    {
        f >> x >> y >> z;
        G[x].pb(mp(y,z));
        G[y].pb(mp(x,z));
    }
    for ( i = 1 ; i <= n ; i++ )
        d[i] = INF;
    st = 1;
    d[st] = 0;
    uz[st] = 1;
    drum[st] = 1;
    q.push(st);
    while(!q.empty())
    {
        long long nod = q.front();
        q.pop();
        uz[nod] = 0;
        for ( vector < pair < long long , long long > > ::iterator j = G[nod].begin(); j!= G[nod].end(); j++ )
        {
            long long x = (*j).first;
            long long c = (*j).second;

            if ( d[x] > d[nod] + c )
            {
                d[x] = d[nod] + c;
                if ( !uz[x] )
                {
                    uz[x] = 1;
                    q.push(x);
                }
            }
        }
    }
    q.push(st);

    while(!q.empty())
    {
        long long nod = q.front();
        q.pop();
        uz[nod] = 0;
        for ( vector < pair < long long , long long > > ::iterator j = G[nod].begin(); j!= G[nod].end(); j++ )
        {
            long long x = (*j).first;
            long long c = (*j).second;

            if ( d[x] == d[nod] + c )
            {
                drum[x] += drum[nod] - val[x][nod];
                drum[x] %= MOD;

                if (drum[nod] != val[x][nod])
                q.push(x);

                val[x][nod] = drum[nod]%MOD;
            }
        }
    }
    //g << drum[fn];
    for (int i = 2; i <= n; ++ i)
        g << drum[i] << " ";
    return 0;
}