#include <iostream>
#include <fstream>
#include <cstdlib>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;
ifstream in("dmin.in");
ofstream out("dmin.out");
const int mod=104659;
const int INF=2e9;
const double marja=1e-9;
vector<pair<int,double>>graf[1505];
double d[1505];
int rez[1505];
bool viz[1505];
priority_queue<pair<double,int>,vector<pair<double,int>>,greater<>>q;
void djk(int start)
{
    d[1]=0;
    rez[1]=1;
    q.push({0,1});
    while(!q.empty())
    {
        int x=q.top().second;
        q.pop();
        //if(viz[x]==0)
         {
           viz[x]=1;
           for(unsigned int k=0; k<graf[x].size(); k++)
            {

                int y=graf[x][k].first;
                double nc=graf[x][k].second;

                if(d[y]-(d[x]+nc)>marja)
                {
                    d[y]=d[x]+nc;
                    rez[y]=rez[x];
                    q.push({d[y],y});
                }
                else
                    if(abs(d[y]-(d[x]+nc))<marja)
                        rez[y]=(rez[y]%mod+rez[x]%mod)%mod;

            }
         }
    }
}
int main()
{   int n,m,x,y;
    double cost;
    in>>n>>m;
    for(int i=1; i<=m; i++)
    {
        in>>x>>y>>cost;
        cost=log(cost);
        graf[x].push_back({y,cost});
        graf[y].push_back({x,cost});
    }
    for(int i=1; i<=n; i++)
        d[i]=INF;

    djk(1);
    for(int i=2; i<=n; i++)
        out<<rez[i]<<" ";

    return 0;
}