#include <bits/stdc++.h>
#define NMAX 1505
#define EPS 1e-9
#define INF (int)2e9
#define MOD 104659

using namespace std;

int egal(double,double);
void read();
void bellmanford();
vector <pair <int,double> > G[NMAX];
int nrd[NMAX],n,m;
double dmin[NMAX];
int main(){
    read();
    bellmanford();
    freopen("dmin.out","w",stdout);
    for (int i=2;i<=n;i++){
        cout<<nrd[i]%MOD<<' ';
    }
}

void bellmanford(){
    dmin[1]=0;
    for (int i=2;i<=n;i++){
        dmin[i]=INF;
    }
    queue <int> q;
    q.push(1);
    nrd[1]=1;
    while (!q.empty()){
        int nod=q.front();
        q.pop();
        for (int i=0;i<G[nod].size();i++){
            int vecin=G[nod][i].first;
            double cost=G[nod][i].second;
            if (dmin[vecin]-EPS>dmin[nod]+cost){
                nrd[vecin]=nrd[nod]%MOD;
                dmin[vecin]=dmin[nod]+cost;
                q.push(vecin);
            }
            else {
                if (egal(dmin[vecin],dmin[nod]+cost)){
                    nrd[vecin]=((nrd[nod]%MOD)+(nrd[vecin]%MOD))%MOD;
                    nrd[vecin]%=MOD;
                }
            }
        }
    }
}

void read(){
    freopen("dmin.in","r",stdin);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++){
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        double nc=log(c);
        G[x].push_back(make_pair(y,nc));
        G[y].push_back(make_pair(x,nc));
    }
}

int egal(double x,double y){
    return abs(x-y)<EPS;
}