#include<fstream>
#include<vector>
#include<set>

using namespace std;

ifstream fin("dmin.in");
ofstream fout("dmin.out");

#define pb push_back
#define NMAX 1503
#define MMAX 2506
#define INF (1<<25);
#define mp make_pair
#define MOD 104659

int n, m;
vector <pair <int, int> > g[NMAX];

void read(){
    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        int x, y, c;
        fin >>x >>y >>c;
        g[x].pb(mp(y,c));
        g[y].pb(mp(x,c));
    }
}

void Dijkstra(int r){
    long long nr_drumuri[NMAX], dist[NMAX];
    for(int i = 1; i <= n; i++) nr_drumuri[i] = 0, dist[i] = INF;

    dist[r] = 1;
    set < pair <int, int> > q;
    q.insert(mp(r, 1));
    nr_drumuri[r] = 1;
    while(! q.empty()){
        int nod = (*q.begin()).first;
        q.erase(*q.begin());

        for(int i = 0 ; i < g[nod].size(); i++){
            int cost = g[nod][i].second;
            int y = g[nod][i].first;

             if(dist[y] ==  dist[nod] * cost){
                nr_drumuri[y] = (nr_drumuri[y] + nr_drumuri[nod] ) %MOD;
            }
            if(dist[y] >  dist[nod] * cost){

                q.insert(mp(y,cost));
                dist[y] = dist[nod] * cost;
                nr_drumuri[y] = nr_drumuri[nod] %MOD;
            }


        }
    }
    for(int i = 2; i<= n ;i++)
        fout << nr_drumuri[i] <<" ";
}
int main(){
    read();
    Dijkstra(1);
    fin.close();
    return 0;

}