#include <fstream>
#include <vector>
#include <set>

using namespace std;

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

const int N = 1505, mod = 104569;
set <pair <int, int> > q;
vector <int> ls[N], lc[N];
int n, m, x, y, c, i, j, l;
int d[N], sol[N];

int main() {
    f >> n >> m;
    while (m--) {
        f >> x >> y >> c;
        ls[x].push_back(y);
        lc[x].push_back(c);
        ls[y].push_back(x);
        lc[y].push_back(c);
    }
    for (i = 2; i <= n; i++)
        d[i] = 1e9;
    sol[1] = 1;
    q.insert(make_pair(0,1));
    set<pair<int, int> >::iterator w;
    while (!q.empty()) {
        x = q.begin() -> second;
        q.erase(q.begin());
        l = ls[x].size();
        for (i = 0; i < l; i++) {
            y = ls[x][i];
            c = lc[x][i];
            if (d[x]+c < d[y]) {
                if ((w = q.find(make_pair(d[y],y))) != q.end())
                    q.erase(w);
                d[y] = d[x]+c;
                sol[y] = sol[x];
                q.insert(make_pair(d[y], y));
            } else if (d[x]+c == d[y])
                sol[y] = (sol[y]+sol[x])%mod;
        }
    }
    for (i = 2; i <= n; i++)
        g << sol[i] << ' ';
}