# include <bits/stdc++.h>
using namespace std;
# define x first
# define y second
ifstream fi("dmin.in");
ofstream fo("dmin.out");
vector < pair < int , double > > s[1555];
const int mod = 104659;
double d[1555];
int cont[1555];
bool ok[1555];
int get(int k)
{
    if (ok[k]) return cont[k];
    ok[k] = 1;
    for (auto it : s[k])
        if (abs(it.y - d[k] + d[it.x]) < 1e-6)
            {
                cont[k] += get(it.x);
                if (cont[k] >= mod) cont[k] -= mod;
            }
    return cont[k];
}
int main(void)
{
    int n,m,a,b,c;
    fi>>n>>m;
    while (m --)
    {
        fi>>a>>b>>c;
        s[a].push_back({b,log(c)});
        s[b].push_back({a,log(c)});
    }
    d[1] = 0;
    cont[1] = 1;
    for (int i = 2;i <= n;++i)
        d[i] = 2e9;
    set < pair < double , int > > q;
    q.insert({0,1});
    while (!q.empty())
    {
        auto it = *q.begin();
        q.erase(q.begin());
        for (auto w : s[it.y])
            if (d[w.x] > d[it.y] + w.y)
                d[w.x] = d[it.y] + w.y,q.insert({d[w.x],w.x});
    }
    ok[1] = 1;
    for (int i = 2;i <= n;++i) cont[i] = get(i);
    for (int i = 2;i <= n;++i) fo << cont[i] << ' ';
    return fo << '\n',0;
}