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

using namespace std;

#define Nmax 1501
#define eps 0.0000001
#define modulo 104659
#define inf 9999999.999

vector < pair <int, double> > Graf[Nmax];
vector <double> dist(Nmax);
vector <int> numar(Nmax);
queue <int> Q;
bitset <Nmax> viz;

int N, M;

void citire(){

    ifstream f("dmin.in");

    f >> N >> M;

    int a, b;
    double c;

    for(; M; M--){

        f >> a >> b >> c;

        Graf[a].push_back(make_pair(b, c));
        Graf[b].push_back(make_pair(a, c));
    }

    f.close();
}

void Dijkstra(){

    vector < pair <int, double> > ::iterator it;

    for(int i = 1; i <= N; i++)
        dist[i] = inf;

    dist[1] = 0;
    numar[1] = 1;
    Q.push(1);

    while(!Q.empty()){

        int nod = Q.front();
        Q.pop();

        for(it = Graf[nod].begin(); it != Graf[nod].end(); ++it)
            if(dist[it->first] > dist[nod] + it->second){

                dist[it->first] = dist[nod] + it->second;
                numar[it->first] = numar[nod];
                Q.push(it->first);
            }
            else
                if(dist[it->first] == dist[nod] + it->second){

                    numar[it->first] += numar[nod];
                    numar[it->first] %= modulo;
                }
    }

}

void afis(){

    ofstream g("dmin.out");

    for(int i = 2; i <= N; i++)
        g << numar[i] << " ";
}

int main(){

    citire();
    Dijkstra();
    afis();

    return 0;
}