#include <iostream>
#include <fstream>
#define maxi 999999999
#define mod 104659
#define N 1501
#define M 2501
#include <queue>
using namespace std;
ifstream f("dmin.in");
ofstream g("dmin.out");
int n,m,start[N], viz[N], t[3][2*M], d[N], cnt[N];
queue <int> q;

void liste_adiacenta()
{
    int x, y, z, i, 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[0][++k] = x; t[1][k] = start[y]; start[y] = k;
        t[2][k] = t[2][k-1] = z;
    }
}

void ford(int nod)
{
    int i, k, x;
    for (i = 1; i <= n; i++)
        d[i] = maxi;
    q.push(nod); d[nod] = 0; cnt[nod] = 1;
    while (!q.empty())
    {
        k = q.front(); viz[k] = 0;
        q.pop();
        x = start[k];
        while (x)
        {
            if (d[k] + t[2][x] < d[t[0][x]])
            {
                d[t[0][x]] = d[k] + t[2][x];
                if (!viz[t[0][x]])
                    q.push(t[0][x]) , viz[t[0][x]] = 1;
                cnt[t[0][x]] = cnt[k];
            }
            else if (d[k] + t[2][x] == d[t[0][x]])
            {
                cnt[t[0][x]] += cnt[t[0][x]];
                cnt[t[0][x]] %= mod;
            }
            x = t[1][x];
        }
    }
}

void afis()
{
    int i;
    for (i = 1; i <= n; i++)
        g << cnt[i] << " ";
}

int main()
{
    f >> n >> m;
    liste_adiacenta();
    ford(1);
    afis();
    return 0;
}