#include <bits/stdc++.h>
using namespace std;
#define INF 1e18
#define MAXN 1505
#define MAXM 5005
#define MOD 104659
int adj[MAXN],urmator[MAXM*2],la[MAXM*2],vizitat[MAXN];
long long c[MAXM*2],nrDrumuri[MAXN];
double dist[MAXN];
int main(){
    ifstream cin ("dmin.in");
    ofstream cout ("dmin.out");
    int n,m,u,v,i,j,iter,nodMin;
    long long cost;
    double distMin,distNoua;
    cin >> n >> m;
    for(i=0;i<n;i++)
        adj[i]=-1;
    for(i=0;i<m;i++){
        cin >> u >> v >> cost;
        u--;
        v--;
        la[i*2]=v;
        c[i*2]=cost;
        urmator[i*2]=adj[u];
        adj[u]=i*2;
        la[i*2+1]=u;
        c[i*2+1]=cost;
        urmator[i*2+1]=adj[v];
        adj[v]=i*2+1;
    }
    for(i=0;i<n;i++){
        dist[i]=INF;
        nrDrumuri[i]=vizitat[i]=0;
    }
    dist[0]=0;
    nrDrumuri[0]=1;
    for(iter=0;iter<n;iter++){
        nodMin=-1;
        distMin=INF;
        for(i=0;i<n;i++){
            if(!vizitat[i]&&dist[i]<distMin){
                distMin=dist[i];
                nodMin=i;
            }
        }
        if(nodMin==-1)
            break;
        vizitat[nodMin]=1;
        for(j=adj[nodMin];j!=-1;j=urmator[j]){
            v=la[j];
            cost=c[j];
            distNoua=dist[nodMin]+log(cost);
            if(distNoua < dist[v]-1e-9){
                dist[v]=distNoua;
                nrDrumuri[v]=nrDrumuri[nodMin];
            }
            else if(fabs(distNoua-dist[v])<1e-9)
                nrDrumuri[v]=(nrDrumuri[v]+nrDrumuri[nodMin])%MOD;
        }
    }
    for(i=1;i<n;i++){
        if(i>1)
            cout << " ";
        cout << nrDrumuri[i];
    }
    return 0;
}