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

const int NMAX = 1505;
const double eps = 1e-10;
const double inf = 100000.0;
const int MOD = 104659;

using namespace std;

ifstream f("dmin.in");
ofstream g("dmin.out");

double Dmin[NMAX];
int N,M,x,y,c;
int d[NMAX];
int dant[NMAX];
vector < pair<int,double> > v[NMAX];
queue <int> Q;
bool inQueue[NMAX];

void bellmanford()
{
    for (int i = 1; i <= N; ++i)
    {
        Dmin[i] = inf;
    }

    Q.push(1);
    d[1] = 1;
    Dmin[1] = 0.0;
    inQueue[1] = true;

    while(!Q.empty())
    {
        int nod = Q.front();
        for (int i = 0; i < v[nod].size(); ++i)
        {
            int vecin = v[nod][i].first;
            double costEnergie = v[nod][i].second;

            if (Dmin[nod] + costEnergie - Dmin[vecin] < -eps)
            {
                dant[vecin] = 0;
                d[vecin] = d[nod];
                Dmin[vecin] = Dmin[nod] + costEnergie;
                if (!inQueue[vecin])
                {
                    Q.push(vecin);
                    inQueue[vecin] = true;
                }
            }
            else
            {
                if (fabs(Dmin[nod] + costEnergie - Dmin[vecin]) <= eps)
                {
                    d[vecin] = (d[vecin] + d[nod] - dant[nod]) % MOD;
                    if (!inQueue[vecin])
                    {
                        Q.push(vecin);
                        inQueue[vecin] = true;
                    }
                }
            }
        }

        dant[nod] = d[nod];

        Q.pop();
        inQueue[nod] = false;
    }
}

int main()
{
    f >> N >> M;

    for (int i = 1; i <= M; ++i)
    {
        f >> x >> y >> c;
        double newc = log(c);
        v[x].push_back(make_pair(y,newc));
        v[y].push_back(make_pair(x,newc));
    }

    bellmanford();

    for (int i = 2; i <= N; ++i)
    {
        g << d[i] << " ";
    }

    f.close();
    g.close();
    return 0;
}