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

#define NRMAX 1501
#define pb push_back
#define mp make_pair
#define INF 10000000.0
#define mod 104659
#define eps 0.0000001

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

int n,m;
vector < pair < int , int > > G[NRMAX];
vector < int > used;
vector < double >  d;
vector < int >  drmin;


void read()
{
    f >> n >> m;
    used = vector < int > (n+1);
    d = vector < double > (n+1,INF);
    drmin = vector < int > (n+1,1);
    for ( ; m-- ; )
    {
        int x,y,z;
        f >> x >> y >> z;
        G[x].pb(mp(y,z));
        G[y].pb(mp(x,z));
    }
}

void bellman ( int i )
{
    queue < int > q;
    d[i] = 0;
    q.push(i);
    drmin[i] = 1;
    used[i] = 1;
    while ( !q.empty() )
    {
        int nod = q.front();
        q.pop();
        for ( vector < pair < int , int > > ::iterator j = G[nod].begin(); j != G[nod].end(); j++ )
        {
            int x = (*j).first;
            int cost = (*j).second;
            if ( d[x] - d[nod] - cost > eps )
            {
                d[x] = d[nod] + cost;
                drmin[x] = drmin[nod]%mod;
                if ( !used[x] )
                {
                    q.push(x);
                    used[x] = 1;
                }
            }
            else
                if( abs( d[x] - d[nod] - cost ) <= eps )
                {
                    drmin[x] += drmin[nod];
                    drmin[x] %= mod;
                }
        }
    }
    for ( i = 2; i <= n ; i++ )
        g << drmin[i] << " ";
}

int main()
{
    read();
    bellman(1);
    return 0;
}