#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];
vector < pair<int,double> > v[nmax];
queue <int> Q;
bool inQueue[nmax];

void solve()
{
    vector <pair <int,double> > :: iterator it;
    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();
        Q.pop();
        inQueue[nod] = false;
        for (it=v[nod].begin(); it!=v[nod].end(); it++)
        {
            int vecin = it->first;
            double costEnergie = it->second;
            if (Dmin[nod] + costEnergie - Dmin[vecin] < -eps)
            {
                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]) % mod;
                    if (!inQueue[vecin])
                    {
                        Q.push(vecin);
                        inQueue[vecin] = true;
                    }
                }
            }
        }
    }
}

int main()
{
    int i;
    f >> n >> m;
    for(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));
    }
    solve();
    for (i = 2; i <= n; ++i)
        g << d[i] << " ";
    f.close();
    g.close();
    return 0;
}