#include <fstream>
#include <vector>
#include <cmath>
#include <queue>
#define NMAX 1510
#define MOD 104659
#define EPS 0.0000000001
#define INF 1000000000

using namespace std;

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

int n, m, in[NMAX], nrd[NMAX];
double D[NMAX];

vector<int> A[NMAX];
vector<double> C[NMAX];
queue<int> Q;


int main()
{
    int i, a, b, nod, vecin;
    double c, cost;
    fin >> n >> m;
    for (i = 1; i <= m; i++)
    {
        fin >> a >> b >> c;
        A[a].push_back(b);
        C[a].push_back(log10(c));
        A[b].push_back(a);
        C[b].push_back(log10(c));
    }
    for (i = 2; i <= n; i++)
        D[i] = INF;
    nrd[1] = 1;
    Q.push(1);
    in[1] = 1;
    while (!Q.empty())
    {
        nod = Q.front();
        Q.pop();
        in[nod] = 0;
        for (i = 0; i < A[nod].size(); i++)
        {
            vecin = A[nod][i];
            cost = C[nod][i];
            if (D[vecin] > D[nod] + cost + EPS)
            {
                D[vecin] = D[nod] + cost;
                nrd[vecin] = nrd[nod] % MOD;
                if (!in[vecin])
                {
                    in[vecin] = 1;
                    Q.push(vecin);
                }
            }
            else if (abs(D[vecin] - D[nod] - cost) < EPS)
                nrd[vecin] = (nrd[vecin] % MOD + nrd[nod] % MOD) % MOD;
        }
    }
    for (i = 2; i <= n; i++)
        fout << nrd[i] << ' ';
    fout << '\n';
    fout.close();
    return 0;
}