#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cmath>
#include <limits>
#define maxi 2000
using namespace std;
ifstream f("dmin.in",ios::in);
ofstream g("dmin.out",ios::out);
using ld96=long double;
using int32=int;
using b1=bool;
const ld96 INF=numeric_limits<long double>::max();
const int32 mod=104659;
vector<pair<int32,int32>> V[maxi];
priority_queue<pair<ld96,int32>,vector<pair<ld96,int32>>,greater<pair<ld96,int32>>> heap;
int32 n,m,dp[maxi];
ld96 D[maxi];
b1 viz[maxi];
void READ()
{
    int a,b,c;
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>a>>b>>c;
        V[a].push_back(make_pair(b,c));
        V[b].push_back(make_pair(a,c));
    }
    f.close();
    return;
}
void INIT()
{
   for(int i=2;i<=n;i++)
     D[i]=INF;
   return;
}
void DIJKSTRA()
{
    dp[1]=1;
    D[1]=0;
    heap.push(make_pair(0,1));
    while(!heap.empty())
    {
        int sursa=heap.top().second;
        viz[sursa]=true;
        heap.pop();
        for(auto a:V[sursa])
        {
            int vecin=a.first;
            int cost=a.second;
            else{
                if(D[sursa]+log(cost)<D[vecin])
                {
                    dp[sursa]=(dp[sursa]+dp[vecin])%mod;
                    D[vecin]=D[sursa]+log(cost);
                    heap.push(make_pair(D[vecin],vecin));
                }
            }
        }
    }
    for(int i=2;i<=n;i++)
        g<<dp[i]<<" ";
    g.close();
    return;
}
int main()
{
    READ();
    INIT();
    DIJKSTRA();
    return 0;
}