#include <cstdio>
#include <cmath>
#include <vector>

#define MOD 104659
#define SIZE 1502
#define eps 0.0000000001
#define inf (1<<30)
#define cst first
#define node2 second

using namespace std;

int n, m, paths[SIZE];
double dist_min[SIZE];
vector < pair< double, int > > adj[SIZE];
bool used[SIZE];

inline void read();
inline void solve();
inline void write();
inline int compare( double, double );

int main()
{
    read();
    solve();
    write();
    return 0;
}

inline void read()
{
    freopen("dmin.in", "r", stdin);
    scanf("%d%d", &n, &m);
    while( m-- )
    {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        double cost = log( c );

        adj[ x ].push_back( make_pair( cost, y ) );
        adj[ y ].push_back( make_pair( cost, x ) );
    }
}

inline void solve()
{
    for(int i = 2; i <= n; ++i)
        dist_min[ i ] = inf;
    paths[ 1 ] = 1;

    for( int i = 1; i <= n; ++i )
    {
        double MIN = inf;
        int node = n + 1;
        for( int j = 1; j <= n; ++j)
            if( ! used[ j ] && dist_min[j] < MIN )
            {
                MIN = dist_min[j];
                node = j;
            }

        if( node == n + 1 )
            return ;
        used[ node ] = 1;

        for( vector < pair< double, int > > :: iterator it = adj[node].begin(); it != adj[node].end(); ++it)
            if( compare(dist_min[ (*it).node2 ], dist_min[ node ] + (*it).cst) == 0 )
            {
                paths[(*it).node2 ] += paths[ node ];
                paths[(*it).node2 ] %= MOD;
            }
            else if( compare(dist_min[ (*it).node2 ], dist_min[ node ] + (*it).cst) == 1)
            {
                dist_min[ (*it).node2 ] = dist_min[ node ] + (*it).cst;
                paths[ (*it).node2 ] = paths[ node ];
            }
    }
}

inline int compare( double x, double y )
{
    if( x > eps + y )
        return 1;
    if( y > x + eps)
        return -1;
    return 0;
}

inline void write()
{
    freopen("dmin.out", "w", stdout);
    for( int i = 2; i <= n; ++i)
        printf("%d ", paths[i] % MOD);
    printf("\n");
}