#include <fstream>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;

ifstream is("dmin.in");
ofstream os("dmin.out");

#define Eps 0.0000000001
#define MOD 104659

int N, M, x,y;
double z, D[15001];
int Nr[15001];
vector <pair<int,double> > G[15001];
priority_queue <pair<int,double>, vector<pair<int,double> >, greater <pair<int,double> > > P;

void Input();
void Dijkstra();

int main()
{
    Input();
    Dijkstra();

    for ( int i = 2; i <= N; ++i )
        os << Nr[i] << " ";
    is.close();
    os.close();
}

void Input()
{
    is >> N >> M;
    for ( int i = 1; i <= M; ++i )
    {
        is >> x >> y >> z;
        G[x].push_back(make_pair(y,log10(z)));
    }
    for ( int i = 1; i <= N; ++i )
        D[i] = 1<<32-1;
    D[1] = 0;
    Nr[1] = 1;
}

void Dijkstra()
{
    P.push(make_pair(1,0));
    vector <pair<int,double> > :: iterator it;
    int nd, cs;
    while ( !P.empty() )
    {
        nd = P.top().first;
        cs = P.top().second;
        P.pop();
        for ( it = G[nd].begin(); it != G[nd].end(); ++it )
        {
            if ( it->second + D[nd] < D[it->first] )
            {
                D[it->first] = it->second + D[nd];
                Nr[it->first] += Nr[nd];
                P.push(make_pair(it->first,D[it->first]));
                Nr[it->first] %= MOD;

            }
            else if ( fabs(((it->second+D[nd])-(D[it->first]))) < Eps )
            {
                Nr[it->first] += Nr[nd];
                Nr[it->first] %= MOD;
            }
        }
    }
}