#include <bits/stdc++.h>

using namespace std;
ifstream fin("dmin.in");
ofstream fout("dmin.out");
const double eps = 0.000001;
const int mod = 104659;

int n, m, nrd[1502];
double d[1502];
struct ura
{
    int nod;
    double cost;
    bool operator < (const ura& aux) const
    {
        return cost > aux.cost;
    }
};
vector<ura> vecini[1502];
priority_queue<ura> q;

int main()
{
    fin>>n>>m;
    for(int i = 1; i <= m; ++i)
    {
        int x, y;
        double c;
        fin>>x>>y>>c;
        c = log2(c);
        vecini[x].push_back({y, c});
        vecini[y].push_back({x, c});
    }

    for(int i = 1; i <= n; ++i)
        d[i] = 1e9+6;

    d[1] = 0;
    nrd[1] = 1;
    q.push({1, 0});
    while(!q.empty())
    {
        ura crt = q.top();
        q.pop();
        if(abs(crt.cost - d[crt.nod]) > eps)
            continue;

        for(auto i : vecini[crt.nod])
        {
            double urm = crt.cost + i.cost;

            if(abs(urm - d[i.nod]) < eps)
                nrd[i.nod] = (nrd[i.nod] + nrd[crt.nod]) % mod;

            else if(urm < d[i.nod])
            {
                nrd[i.nod] = nrd[crt.nod];
                d[i.nod] = urm;
                q.push({i.nod, urm});
            }
        }
    }
    for(int i = 2; i <= n; ++i)
        fout<<nrd[i]<<" ";


    return 0;
}