#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <iostream>

#define x first
#define y second

using namespace std;

const int NMAX = 1507;
const int INF = 10000000000;
const int Mod = 104659;

priority_queue< pair< int, int > > q;
int D[NMAX], Dp[NMAX], Viz[NMAX];
vector< pair< int, int > > v[NMAX];
int n, m;

void Dijkstra(){
    for(int i = 2 ; i <= n ; ++ i)
        D[i] = INF;
    q.push(make_pair(0 , 1));
    while(! q.empty()){
        int Nod = q.top().y;
        q.pop();
        if(Viz[Nod] == 0){
            Viz[Nod] = 1;
            for(vector< pair< int, int> >::iterator it = v[Nod].begin() ; it != v[Nod].end() ; ++ it)
                if(D[it->x] >= D[Nod] + it->y){
                    if(D[it->x] == D[Nod] + it->y){
                        Dp[it->x] += Dp[Nod];
                        Dp[it->x] %= Mod;
                    }
                    else
                        Dp[it->x] = Dp[Nod] % Mod;
                    D[it->x] = D[Nod] + it->y;
                    q.push(make_pair(-D[it->x] , it->x));
                }
        }
    }
}


int main(){
    freopen("dmin.in", "r", stdin);
    freopen("dmin.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; ++i){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        v[a].push_back(make_pair(b, c));
        v[b].push_back(make_pair(a, c));
    }
    for(int i = 1; i <= n; ++i)
        Dp[i] = 1;
    Dijkstra();
    for(int i = 2; i <= n; ++i)
        printf("%d ", Dp[i]);
    return 0;
}