#include<fstream>
#include<vector>
#include<cmath>
#include<queue>

using namespace std;
typedef int64_t var;

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

struct Edge {
    var n, c;
    Edge(var a, var b) {
        n = a;
        c = b;
    }
};
#define MAXN 1501

vector<Edge> G[MAXN];
var n;
double D[MAXN];
var D_R[MAXN];
var NR[MAXN];
bool INQ[MAXN];

#define P 104659
#define INF (1 << 28)
#define eps 1e-12

void bellman() {
    for(var i=1; i<=n; i++) {
        D[i] = INF;
    }
    D[1] = 0;
    NR[1] = 1;
    queue<var> Q;
    Q.push(1);
    while(!Q.empty()) {
        var node = Q.front();
        Q.pop();
        INQ[node] = 0;
        for(auto e : G[node]) {
            if(D[e.n] > D[node] + log(e.c) + eps) {
                D[e.n] = D[node] + log(e.c);
                D_R[e.n] = (D_R[node] * e.c) % 10000;
                NR[e.n] = 0;
                if(!INQ[e.n]) {
                    Q.push(e.n);
                    INQ[e.n] = 1;
                }
            }
            if(abs(D[e.n] - (D[node] + log(e.c))) < eps && D_R[e.n] == (D_R[node] * e.c) % 10000 ) {
                NR[e.n] += NR[node];
                NR[e.n] %= P;
            }
        }
    }
}

int main() {
    var a, b, m;
    var c;
    fin>>n>>m;
    while(m--) {
        fin>>a>>b>>c;
        G[a].push_back(Edge(b, c));
        G[b].push_back(Edge(a, c));
    }
    bellman();
    for(var i=2; i<=n; i++) {
        fout<<NR[i]<<" ";
    }
    return 0;
}