#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <cmath>
#define pb push_back
#define nl '\n'
using namespace std;
ifstream f ( "dmin.in" );
ofstream g ( "dmin.out" );
const int NMAX = 1501, MOD = 104659;
const double EPS = 1e-9, INF = 1e+9;
struct muchie
{
    int y;
    double w;
};
int N, M;
double D[NMAX];///D[i] = distanta minima de la nodul srd la i
int nrD[NMAX];///nrD[i] = numarul de drumuri de lungime D[i]
vector<muchie>G[NMAX];
queue<int>Q;
bool inQ[NMAX];/// daca este in coada
void citire()
{
    int x, y, c;
    double w;
    f >> N >> M;

    while ( M-- )
    {
        f >> x >> y >> c;
        w = log ( c );
        G[x].pb ( {y, w} );
        G[y].pb ( {x, w} );
    }
}
void init ( int src )
{
    for ( int i = 1; i <= N; i++ )
        D[i] = INF;

    D[src] = 0;
}
void BellmanFord ( int src )
{
    int crt, dest;
    double cost;
    init ( src );
    Q.push ( src );
    inQ[src] = 1;
    nrD[src] = 1;

    while ( !Q.empty() )
    {
        int crt = Q.front();
        Q.pop();

        for ( muchie &m : G[crt] )
        {
            cost = D[crt] + m.w;
            dest = m.y;

            if ( fabs ( cost - D[dest] ) <= EPS )
                nrD[dest] = ( nrD[dest] + nrD[crt] ) % MOD;
            else
                if ( D[dest] - cost > EPS )
                {
                    D[dest] = cost;
                    nrD[dest] = nrD[crt];

                    if ( inQ[dest] == 0 )
                    {
                        Q.push ( dest );
                        inQ[dest] = 1;
                    }
                }
        }
    }
}
int main()
{
    citire();
    BellmanFord ( 1 );

    for ( int i = 2; i <= N; i++ )
        g << nrD[i] << ' ';

    f.close();
    g.close();
    return 0;
}