#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;

#define Nmax 1502
#define Mod 104659

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

const long long inf = 1000000000000000000;

int N, M, Aport[Nmax];
long long Dist[Nmax];
vector < pair < int, int > > G[Nmax];
bitset < Nmax > inQ;
queue < int > Q;

void BellmanFord(){

    for ( int i = 2; i <= N; ++i )
        Dist[i] = inf;

    Aport[1] = 1;
    Q.push ( 1 );
    inQ[1] = 1;

    vector < pair < int, int > > :: iterator it;
    while ( !Q.empty() ){
        int nod = Q.front();
        Q.pop();
        inQ[nod] = 0;

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

                Aport[it->first] = Aport[nod];

                if ( !inQ[it->first] ){
                    Q.push ( it->first );
                    inQ[it->first] = 1;
                }
            }
            else if ( Dist[nod] + it->second == Dist[it->first] ){
                Aport[it->first] += Aport[nod];
                Aport[it->first] %= Mod;
            }
        }
    }
}

int main(){

    int x, y, c;

    fin >> N >> M;

    while ( M-- ){
        fin >> x >> y >> c;
        G[x].push_back ( make_pair ( y, c ) );
        G[y].push_back ( make_pair ( x, c ) );
    }

    BellmanFord();

    for ( int i = 2; i <= N; ++i )
        fout << Aport[i] << " ";

    return 0;
}