#include <fstream>
#include <deque>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <cmath>
#include <climits>

#define MOD 104659

using namespace std ;

ifstream cin ("dmin.in") ;
ofstream cout ("dmin.out") ;

int n ;

vector<pair<long long, double> > v[1509] ;

double cost[1509] ;

long long drumuri[1509] ;

void fil()
{
    priority_queue<pair<double, pair<long long, long long> > > pq ;

    pq.push({-1, {1, 1}}) ;

    drumuri[1] = 1 ;
    cost[1] = -1 ;

    while(pq.size())
    {
        pair<double, pair<long long, long long> > curent ;

        curent = pq.top() ;

        pq.pop() ;

        int nod = curent.second.first ;
        double ccost = curent.first ;
        long long ddrumuri = curent.second.second ;

        if(!drumuri[nod] || ccost == cost[nod])
        {
        drumuri[nod] += ddrumuri % MOD ;
        drumuri[nod] %= MOD ;
        cost[nod] = ccost ;

        for(int f = 0 ; f < v[nod].size() ; f ++)
            pq.push({ccost * v[nod][f].second * -1, {v[nod][f].first, ddrumuri % MOD}}) ;
        }
    }
}

int main()
{
    int q;

    cin >> n >> q ;

    while(q --)
    {
        int a, b ;

        double c ;

        cin >> a >> b >> c ;

        c = log2(c) + 1 ;

        v[a].push_back({b, c}) ;
        v[b].push_back({a, c}) ;
    }

    fil() ;

    for(int f = 2 ; f <= n ; f ++)
        cout << drumuri[f] << " " ;

    return 0 ;
}
/*
10 3
54 36 17 77 21 74 75 0 73 106
1 6 13427
1 4 6289
0 10 10
1 1 370
1 9 33
1 10 12273
0 8 9
0 8 9
1 7 3620
0 5 9
1 10 35
0 8 8
0 2 2
0 5 10
1 3 23314
0 1 5
0 2 9
1 9 33
1 10 9129
0 5 5
1 2 49
*/