#include <iostream>
#include <fstream>
#define L 1505
#define INF 99999999
#define mod 104659
using namespace std;
ifstream f("dmin.in");
ofstream g("dmin.out");

int viz[L], t[3][(L * (L - 1)) / 2], n, m, cst, p, k, start[L], pi, ps, x, y, v[L], ki;
long long cost[L], c[(L * (L - 1)) / 2];

void ford(int p)
{
    int x;
    pi = ps = 1;
    c[pi] = p;
    viz[p] = 1;
    v[p] = 1;
    while(ps <= pi)
    {
        x = start[c[ps]];
        viz[c[ps]] = 0;
        while(x)
        {
            if(cost[c[ps]] + t[2][x] < cost[t[0][x]])
            {
                cost[t[0][x]] = cost[c[ps]] + t[2][x];
                if(!viz[t[0][x]])
                {
                    c[++pi] = t[0][x];
                    viz[t[0][x]] = 1;
                }
                v[t[0][x]] = v[c[ps]] % mod;
            }
            else
            if(cost[c[ps]] + t[2][x] == cost[t[0][x]])
            {
                v[t[0][x]] = (v[t[0][x]] + v[c[ps]]) % mod;
            }
            x = t[1][x];
        }
        ps++;
    }
}

int main()
{
    f >> n >> m;
    while(f >> x >> y >> cst)
    {
        k++;
        t[0][k] = y;
        t[1][k] = start[x];
        start[x] = k;
        t[2][k] = cst;
        k++;
        t[0][k] = x;
        t[1][k] = start[y];
        start[y] = k;
        t[2][k] = cst;
    }
    for(int i = 1; i <= n; i++)
        cost[i] = INF;
    cost[1] = 0;
    ford(1);
    for(int i = 2; i <= n; i++)
        g << v[i] << " ";

    return 0;
}