#include <bits/stdc++.h>

#define MOD 104659
#define EPS 0.0000000001
#define f first
#define s second

using namespace std;

ifstream F("dmin.in");
ofstream G("dmin.out");

int n, m, x, y;
long long k[1505];
double d[1505], c;
vector<pair<int, double> > a[1505];
queue<int> q;
bitset<1505> w;

int main()
{
    F >> n >> m;
    for(int i = 0; i < m; ++ i)
    {
        F >> x >> y >> c;
        c = log10(c);
        a[x].push_back({y, c});
        a[y].push_back({x, c});
    }
    for(int i = 2;i <= n; ++ i) d[i] = 2000000000;
    q.push(1); d[1] = 0; k[1]=1;w[1] = 1;
    vector<pair<int, double> > :: iterator it;
    while(!q.empty())
    {
        x = q.front(); q.pop();w[x] = 0;
        for(it = a[x].begin(); it != a[x].end(); ++it)
        {
            y = (*it).f;
            if(d[(*it).f]-EPS > (*it).s+d[x])
            {
                d[(*it).f] = (*it).s+d[x];
                k[(*it).f] = k[x];
                if(!w[(*it).f]) w[(*it).f] = 1, q.push((*it).f);
            }
            else if(abs(d[(*it).f] - ((*it).s+d[x])) < EPS)
            {
                k[(*it).f] += k[x];
                if(k[(*it).f] >= MOD) k[(*it).f] -= MOD;
                if(!w[(*it).f]) w[(*it).f] = 1, q.push((*it).f);
            }
        }
    }
    for(int i = 2;i <= n; ++ i) G << k[i] << " ";
    return 0;
}