#include <bits/stdc++.h>

#define error 1e-9
#define MODULO 104659

using namespace std;

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

#define cin  fin
#define cout fout

#define Nmax 1510
#define infinit INT_MAX

int n;

vector < pair < int , double > > g[Nmax];
double d[Nmax];
int solutie[Nmax];
bool viz[Nmax];

struct cmp {
    bool operator()(int a, int b) {
        return d[a] > d[b];
    }
};

priority_queue < int, vector < int >, cmp > c;

void read() {
    int m;
    cin >> n >> m;
    while(m--) {
        int x, y, cost;
        cin >> x >> y >> cost;
        g[x].push_back({y, (double) log2((double)cost)});
        g[y].push_back({x, (double) log2((double)cost)});
    }
}

void DJ(int nod) {

    for(int i=1; i<=n; i++) {
        d[i] = infinit;
    }

    c.push(nod);
    d[nod] = 0;
    viz[nod] = 1;
    solutie[1] = 1;

    while(!c.empty()) {
            int nod = c.top();
            c.pop();
            viz[nod] = 0;

            for(size_t i = 0; i < g[nod].size(); i++) {
                int vecin = g[nod][i].first;
                double cost  = g[nod][i].second;

                if(d[vecin] > d[nod] + cost || (d[vecin] < d[nod] + cost + error && d[vecin] > d[nod] + cost - error)) {

                    if(d[vecin] < d[nod] + cost + error && d[vecin] > d[nod] + cost - error) {
                        solutie[vecin] = (solutie[vecin] + solutie[nod]) % MODULO;
                    } else {
                        solutie[vecin] = solutie[nod] % MODULO;
                        if(viz[vecin] == 0) {
                            c.push(vecin);
                            viz[vecin] = 1;
                        }
                        d[vecin] = d[nod] + cost;
                    }
                }
            }
     }
}


void solve() {
    DJ(1);

    for(int i=2; i<=n; i++) {
        cout << solutie[i] % MODULO << " ";
    }
}

int main() {
    read();
    solve();
}