#include<fstream>
#include<vector>
#include<cmath>
#define f first
#define s second
#define eps 0.000000001
#define DIM 1505
#define mod 104659
#define INF 1000000000
using namespace std;
int n, m, i, x, y, nod, vecin, cost, j;
int viz[DIM], num[DIM], h[DIM], poz[DIM];
double d[DIM], cost2;
vector< pair<int, double> > v[DIM];
ifstream fin("dmin.in");
ofstream fout("dmin.out");
double modul(double x){
    if(x > 0){
        return x;
    }
    return -x;
}
void upd(int pos){
    int c = pos, p = c / 2;
    while(p > 0 && d[ h[p] ] > d[ h[c] ]){
        swap(h[p], h[c]);
        poz[ h[p] ] = p;
        poz[ h[c] ] = c;
        c = p;
        p = c / 2;
    }
}
void elim(){
    int p = 1, c = 2;
    while(c <= n){
        if(c + 1 <= n && d[ h[c] ] > d[ h[c + 1] ]){
            c++;
        }
        if(d[ h[p] ] > d[ h[c] ]){
            swap(h[p], h[c]);
            poz[ h[p] ] = p;
            poz[ h[c] ] = c;
            p = c;
            c = 2 * p;
        }
        else{
            break;
        }
    }
}
int main(){
    fin>> n >> m;
    for(i = 1; i <= m; i++){
        fin>> x >> y >> cost;
        cost2 = log(cost);
        v[x].push_back( make_pair(y, cost2) );
        v[y].push_back( make_pair(x, cost2) );
    }
    for(i = 1; i <= n; i++){
        d[i] = INF;
        h[i] = poz[i] = i;
    }
    d[1] = 0;
    num[1] = 1;
    for(i = 1; i <= n; i++){
        nod = h[1];
        for(j = 0; j < v[nod].size(); j++){
            vecin = v[nod][j].f;
            if(viz[vecin] == 0){
                if(modul(d[vecin] - d[nod] - v[nod][j].s) <= eps){
                    num[vecin] += num[nod];
                    if(num[vecin] >= mod){
                        num[vecin] -= mod;
                    }
                }
                else{
                    if(d[nod] + v[nod][j].s < d[vecin]){
                        d[vecin] = d[nod] + v[nod][j].s;
                        upd(poz[vecin]);
                        num[vecin] = num[nod];
                    }
                }
            }
        }
        viz[nod] = 1;
        d[nod] = INF;
        elim();
    }
    for(i = 2; i <= n; i++){
        fout<< num[i] <<" ";
    }
    return 0;
}