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

using namespace std;

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

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

Nod noduri[NMAX];

void aflaCosturi(int start);
void aflaDrumuri(int start, int n);
bool cmpNoduri(int n1, int n2);
bool estePredecesor(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;
        double c;
        fin >> x >> y >> c;
        c = log2(c);

        noduri[x].vecini.push_back(make_pair(y, c));
        noduri[y].vecini.push_back(make_pair(x, c));
    }

    aflaCosturi(1);

    aflaDrumuri(1, n);

//    for (int i = 1; i <= n; ++i) {
//        cout << i << ": ";
//        for (int pred : noduri[i].predecesori)
//            cout << pred << " ";
//        cout << "\n";
//    }

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

    return 0;
}

void aflaDrumuri(int start, int n)
{
    queue<int> q;
    q.push(start);

    noduri[start].drumuriMinime = 1;
    noduri[start].inCoada = true;

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

        //cout << curent << "\n";

        for (int i = 1; i <= n; ++i) {
            if (i != curent && estePredecesor(curent, i)) {
                noduri[i].drumuriMinime += noduri[curent].drumuriMinime;
                noduri[i].drumuriMinime %= NUMAR_MODULO;
            }
        }

        for (auto muchie : noduri[curent].vecini) {
            int vecin = muchie.first;
            if (!noduri[vecin].inCoada) {
                q.push(vecin);
                noduri[vecin].inCoada = true;
            }
        }
    }
}

bool estePredecesor(int n1, int n2)
{
    return noduri[n2].predecesori.find(n1) != noduri[n2].predecesori.end();
}

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

    noduri[start].costMinim = 0;

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

        noduri[curent].inCoada = false;

        for (auto muchie : noduri[curent].vecini) {
            int vecin = muchie.first;
            int costNou = noduri[curent].costMinim + muchie.second;

            if (costNou < noduri[vecin].costMinim) {
                noduri[vecin].costMinim = costNou;
                noduri[vecin].predecesori.clear();
                noduri[vecin].predecesori.insert(curent);

                if (!noduri[vecin].inCoada) {
                    q.push(vecin);
                    noduri[vecin].inCoada = true;
                }
            }
            else if (abs(costNou - noduri[vecin].costMinim) <= EPSILON) {
                noduri[vecin].predecesori.insert(curent);
            }
        }
    }
}

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