#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 1505;
const int mod = 104659;
const long long inf = LLONG_MAX;
int n,m,viz[NMAX],ans[NMAX];
long long dist[NMAX];
vector < pair < int, long long > > v[NMAX];
priority_queue < pair < long long, int > > q,d;

int main(){
    int i,x,y,node;
    long long z,cost,value;
    f >> n >> m;
    for(i = 1 ; i <= m ; i++){
        f >> x >> y >> z;
        //z = log2(z);
        v[x].push_back(make_pair(y,z));
        v[y].push_back(make_pair(x,z));
    }

    for(i = 2 ; i <= n ; i++)
        dist[i] = inf;

    q.push(make_pair(0, 1));
    while(!q.empty()){
        node = q.top().second;
        cost = -q.top().first;
        q.pop();

        if(viz[node])
            continue;
        viz[node] = 1;

        for(auto it: v[node]){
            value = dist[node] + it.second;
            if(dist[it.first] > value){
                dist[it.first] = value;
                d.push(make_pair(-value, it.first));
                q.push(make_pair(-value, it.first));
            }else
                if(dist[it.first] == value){
                    d.push(make_pair(-value, it.first));
                }
        }
    }

    memset(viz, 0, sizeof(viz));

    ans[1] = 1;
    d.push(make_pair(0, 1));
    while(!d.empty()){
        node = d.top().second;
        cost = -d.top().first;
        d.pop();

        if(viz[node])
            continue;
        if(cost != dist[node])
            continue;

        viz[node] = 1;

        for(auto it: v[node]){
            value = cost + it.second;
            if(dist[it.first] == value)
                ans[it.first] = (ans[it.first] + ans[node]) % mod;
        }
    }

    for(i = 2 ; i <= n ; i++)
        g << ans[i] << " ";

    return 0;
}