#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;

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

const int nMax = 1505, MOD = 104659;
const double eps = 1e-10;
const double Inf=0x3f3f3f3f;

vector<vector<pair<int,double>>> G;
queue<int> Q;

int n, m, x, y, z, D[nMax];
bool v[nMax];
double Dmin[nMax];

void Read();


void Solve();


int main()
{
    Read();
    Solve();
    for(int i = 2; i <= n;i++)
        fout << D[i] << ' ';
}
void Read()
{

    fin >> n >> m;
    G = vector<vector<pair<int, double>>>( n + 1, vector<pair<int, double>>() );
    for(int i=1;i<=m;i++)
    {
        fin >> x >> y >> z;
        double z1=log(z);
        G[x].push_back({y,z1});
        G[y].push_back({x,z1});
    }
}

void Solve()
{
    for(int i=1;i<=n;i++)
        Dmin[i]=Inf;

    Q.push(1);
    D[1]=1;Dmin[1]=0.0;v[1]=true;
    while(!Q.empty())
    {
        int nod=Q.front();
        Q.pop();
        v[nod]=false;
        for(vector<pair<int,double> >::iterator it=G[nod].begin();it!=G[nod].end();it++)
        {
            int vecin=it->first;
            double cost=it->second;
            if(Dmin[nod]+cost-Dmin[vecin]< -eps)
            {
                D[vecin]=D[nod];
                Dmin[vecin]=Dmin[nod]+cost;
                if(!v[vecin])
                {
                    Q.push(vecin);
                    v[vecin]=true;
                }
            }
            else
            {
                if(fabs(Dmin[nod]+cost-Dmin[vecin])<=eps)
                {
                    D[vecin]=(D[vecin]+D[nod])%MOD;
                    if (!v[vecin])
                    {
                        Q.push(vecin);
                        v[vecin]=true;
                    }
                }
            }
        }
    }
}