# include <cstdio>
# include <cstring>
# include <cmath>
# include <deque>
# include <vector>
using namespace std;

# define x first
# define y second

typedef double db;
const char *FIN = "dmin.in", *FOU = "dmin.out";
const int MAX = 1505, oo = 0x3f3f3f3f, MOD = 104659;
const db eps = 1e-9;

vector < pair <int, db> > G[MAX];
int N, M, T[MAX];
db z, dp[MAX];

inline void _mod (int &a) {
    if (a >= MOD) a -= MOD;
    if (a >= MOD) a %= MOD;
}

void solve (void) {
    deque <int> Q;
    bool viz[MAX];

    for (int i = 1; i < MAX; ++i) dp[i] = oo;
    memset (viz, 0, sizeof (viz));
    dp[1] = .0, T[1] = 1;
    for (Q.push_back (viz[1] = 1); ! Q.empty (); Q.pop_front ()) {
        int act = Q.front (); viz[act] = 0;
        for (vector < pair <int, db> > :: iterator it = G[act].begin (); it != G[act].end (); ++it) {
            if (fabs (dp[act] + it -> y - dp[it -> x]) < eps)
                T[it -> x] += T[act], _mod (T[it -> x]);
            if (dp[it -> x] - dp[act] - it -> y > eps) {
                dp[it -> x] = dp[act] + it -> y;
                T[it -> x] = T[act];
                if (viz[it -> x] == 0) {
                    Q.push_back (it -> x);
                    viz[it -> x] = 1;
                }
            }
        }
    }
}

int main (void) {
    freopen (FIN, "r", stdin);
    freopen (FOU, "w", stdout);

    scanf ("%d %d", &N, &M);
    for (int i = 1, x, y; i <= M; ++i) {
        scanf ("%d %d %lf", &x, &y, &z), z = log (z);
        G[x].push_back (make_pair (y, z));
        G[y].push_back (make_pair (x, z));
    }
    solve ();
    for (int i = 2; i <= N; ++i)
        printf ("%d ", T[i]);
}