#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <queue>

///#include <tryhardmode>
///#include <GODMODE::ON>

using namespace std;

ifstream fin("dmin.in");
ofstream fout("dmin.out");

const int NMAX=15e2+5;
const double marja=1e-9;
const int MOD=104659;
const int INF=2e9;

double dist[NMAX];
bool viz[NMAX];
int total[NMAX];

vector<pair<int,double>>v[NMAX];
priority_queue<pair<double,int>>q;

double make_absolute(double x)
{
    if(x<0)
        return -x;
    return x;
}

void dijkstra2(int p)
{
    dist[p]=0;
    viz[p]=1;
    total[1]=1;
    q.push(make_pair(0,p));
    while(!q.empty())
    {
        long long p=q.top().second;
        q.pop();
        viz[p]=0;
        for(auto i:v[p])
        {
            if(dist[i.first]-(dist[p]+i.second)>marja)
            {
                dist[i.first]=dist[p]+i.second;
                if(viz[i.first]==0)
                {
                    viz[i.first]=1;
                    total[i.first]=total[p];
                    q.push(make_pair(-dist[i.first],i.first));
                }
            }
            else if(make_absolute(dist[p]-dist[i.first]+i.second)<marja && viz[i.first]==0)
                total[i.first]=(total[i.first]+total[p])%MOD,viz[i.first]=1;
        }
    }
}

void dijkstra(int p)
{
    dist[p]=1;
    total[1]=1;
    q.push(make_pair(0,p));
    while(!q.empty())
    {
        long long p=q.top().second;
        q.pop();
        if(viz[p]==0)
        {
            for(auto i:v[p])
            {
                if(dist[i.first]-(dist[p]+i.second)>marja)
                {
                    dist[i.first]=dist[p]+i.second;
                    total[i.first]=total[p];
                    q.push(make_pair(-dist[i.first],i.first));
                }
                else if(make_absolute(dist[p]-(dist[i.first]-i.second))<marja)
                    total[i.first]=(total[i.first]+total[p])%MOD;
            }
            viz[p]=1;
        }
    }
}

int main()
{
    int n,m,x,y,i,j;
    double c;
    fin>>n>>m;
    for(i=1;i<=n;i++)
        dist[i]=INF;
    while(m--)
    {
        fin>>x>>y>>c;
        c=log(c);
        v[x].push_back(make_pair(y,c));
        v[y].push_back(make_pair(x,c));
    }
    dijkstra(1);
    for(i=2;i<=n;i++)
        fout<<total[i]<<" ";
    return 0;
}