#include <bits/stdc++.h>
#define MOD 104659

using namespace std;

ifstream fin("dmin.in");
ofstream fout("dmin.out");

int n, m;
int d[1505], viz[1505];
vector < pair < int, int > > L[1505];
priority_queue < pair < int, int > > Q;
int nrd[1505];

void Read()
{
    int i, x, y, cost;
    fin >> n >> m;
    for(i = 1; i <= m; i++)
    {
        fin >> x >> y >> cost;
        L[x].push_back({y, cost});
        L[y].push_back({x, cost});
    }
    for(i = 1; i <= n; i++)
        d[i] = 1e9;
}

void Dijkstra()
{
    int nod, nodnou, cost;
    Q.push({0, 1});
    d[1] = 0;
    while(!Q.empty())
    {
        nod = Q.top().second;
        Q.pop();
        if(viz[nod] == 0)
        {
            viz[nod] = 1;
            for(auto w : L[nod])
            {
                nodnou = w.first;
                cost = w.second;
                if(nod == 1)
                {
                    if(d[nodnou] == d[nod] + cost)
                        nrd[nodnou] += nrd[nod] % MOD;
                    if(d[nodnou] > d[nod] + cost)
                    {
                        d[nodnou] = d[nod] + cost;
                        Q.push({-d[nodnou], nodnou});
                        nrd[nodnou] = 1;

                    }
                }
                else
                {
                    if(d[nodnou] == d[nod] * cost)
                        nrd[nodnou] += nrd[nod] % MOD;
                    if(d[nodnou] > d[nod] * cost)
                    {
                        d[nodnou] = d[nod] * cost;
                        Q.push({-d[nodnou], nodnou});
                        nrd[nodnou] = nrd[nod];
                    }
                }
            }
        }
    }
}

void Afisare()
{
    int i;
    for(i = 2; i <= n; i++)
        fout << nrd[i] << " ";
    fout << "\n";
}

int main()
{
    Read();
    Dijkstra();
    Afisare();
    return 0;
}