#include <bits/stdc++.h>
#define mod 104659
using namespace std;
ifstream in("dmin.in");
ofstream out("dmin.out");
struct muchie{
    int vecin;
    long double cost;
};
long double e=0.0000000001;
long double dr[1505];
vector <muchie> lista[1505];
struct compare{
    bool operator()(int d1,int d2)
    {
        return dr[d1]>dr[d2];
    }
};
int nrdr[1505],ap[1505];
priority_queue<int,vector<int>,compare> pq;
int main()
{
    int n,m;
    in >> n >> m;
    for(int i=1; i<=n; i++)
    {
        dr[i]=1000000005;
    }
    for(int i=0; i<m; i++)
    {
        int x,y,c;
        in >> x >> y >> c;
        long double o=c;
        o=log10(o);
        lista[x].push_back({y,o});
        lista[y].push_back({x,o});
    }
    pq.push(1);
    nrdr[1]=1;
    dr[1]=0;
    ap[1]=1;
    while(!pq.empty())
    {
        int nod=pq.top();
        ap[nod]=0;
        pq.pop();
        for(int i=0; i<lista[nod].size(); i++)
        {
            int vecin=lista[nod][i].vecin;
            long double cost=lista[nod][i].cost;
            if(dr[vecin]-e>(dr[nod]+cost))
            {
                dr[vecin]=dr[nod]+cost;
                nrdr[vecin]=nrdr[nod];
                if(!ap[nod])
                    ap[nod]=1,pq.push(vecin);
            }
            else if(fabs(dr[vecin]-dr[nod]-cost)<=e)
            {
                nrdr[vecin]=(nrdr[vecin]+nrdr[nod])%mod;
            }
        }
    }
    for(int i=2; i<=n; i++)
    {
        out << nrdr[i] << ' ';
    }
    return 0;
}