#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

#define NMAX 1501
#define NUMAR_MODULO 104659
#define INFINIT 0x3F3F3F3F

struct Nod
{
    vector< pair<int, int> > vecini;
    int costMinim;
    int drumuriMinime;
    bool inCoada;
};

Nod noduri[NMAX];

void aflaDrumuri(int start);
bool cmpNoduri(int n1, int n2);

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

    int n, m;
    fin >> n >> m;

    for (int i = 1; i <= n; ++i) {
        noduri[i].costMinim = INFINIT;
    }

    while (m--) {
        int x, y, c;
        fin >> x >> y >> c;
        noduri[x].vecini.push_back(make_pair(y, c));
        noduri[y].vecini.push_back(make_pair(x, c));
    }

    aflaDrumuri(1);

    for (int i = 2; i <= n; ++i) {
        fout << noduri[i].drumuriMinime << " ";
    }

    return 0;
}

void aflaDrumuri(int start)
{
    priority_queue<int, vector<int>, decltype(&cmpNoduri)> q(&cmpNoduri);
    q.push(start);

    noduri[start].drumuriMinime = 1;
    noduri[start].costMinim = 1;

    while (!q.empty()) {
        int curent = q.top();
        q.pop();

        noduri[curent].inCoada = false;

        for (auto muchie : noduri[curent].vecini) {
            int vecin = muchie.first;
            int cost = muchie.second;
            int costNou = (noduri[curent].costMinim % NUMAR_MODULO) * (cost % NUMAR_MODULO) % NUMAR_MODULO;
            bool schimbareNod = false;

            if (costNou < noduri[vecin].costMinim) {
                noduri[vecin].costMinim = costNou;
                noduri[vecin].drumuriMinime = noduri[curent].drumuriMinime;
                schimbareNod = true;
            }
            else if (costNou == noduri[vecin].costMinim) {
                noduri[vecin].drumuriMinime += noduri[curent].drumuriMinime;
                schimbareNod = true;
            }

            if (schimbareNod && !noduri[vecin].inCoada) {
                q.push(vecin);
                noduri[vecin].inCoada = true;
            }
        }
    }
}

bool cmpNoduri(int n1, int n2)
{
    return noduri[n1].costMinim > noduri[n2].costMinim;
}