#include <fstream>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <set>

using namespace std;

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

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

int main() {
    f >> n >> m;
    while (m--) {
        f >> x >> y >> c;
        c = log10(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] = 1e12;
    sol[1] = 1;
    q.insert(make_pair(0,1));
    set<pair<double, 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]-EPS) {
                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 (abs(d[x]+c - d[y]) < EPS) {
                sol[y] = (sol[y]+sol[x])%mod;
            }
        }
    }
    for (i = 2; i <= n; i++)
        g << sol[i] << ' ';
}