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

using namespace std;

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

const int MAXN = 1500 + 10;
const long double EPS = 1e-9;
const long double INF = 1e20;
const int MOD = 104659;

typedef pair <int, long double> PID;

int N;
vector <PID> Graf[MAXN];
long double Best[MAXN];
int Ans[MAXN];

long double _abs (const long double &A)
{
    if (A < 0)
        return -A;

    return A;
}

struct comp
{
    inline bool operator () (const int &A, const int &B) const
    {
        return Best[A] > Best[B];
    }
};
priority_queue <int, vector <int>, comp> Q;

void Dijkstra ()
{
    int nod;
    int i;
    vector <PID> :: iterator it;

    for (i = 2; i <= N; i ++)
        Best[i] = INF;

    Q.push (1);
    Ans[1] = 1;

    while (!Q.empty ()){
        nod = Q.top ();
        Q.pop ();

        for (it = Graf[nod].begin (); it != Graf[nod].end (); ++ it){
            const int next = (it -> first),
                        cost = (it -> second);

            if (_abs (Best[nod] + cost - Best[next]) < EPS){
                Ans[next] = (Ans[nod] + Ans[next]) % MOD;
            }
            else
                if (Best[nod] + cost - Best[next] < -EPS){
                    Best[next] = Best[nod] + cost;
                    Ans[next] = Ans[nod];
                    Q.push (next);
                }
        }
    }
}

int main()
{
    int M, a, b, c;
    int i;
    long double new_cost;

    in >> N >> M;

    for (i = 1; i <= M; i ++){
        in >> a >> b >> c;
        new_cost = log (c);

        Graf[a].push_back (make_pair (b, c));
        Graf[b].push_back (make_pair (a, c));
    }

    Dijkstra ();

    for (i = 2; i <= N; i ++)
        out << Ans[i] << " ";

    return 0;
}