#include <iostream>
#include <fstream>
#include <queue>
#include <cmath>
using namespace std;

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

const int N_max = 1502;
const int M_max = 2502;
const int mod = 104659;
const long double eps = (long double) 1e-10;

int vf[2 * M_max];
int urm[2 * M_max];
long double cost[2 * M_max];
int lst[N_max];
int nr;

queue <int> C;

long double d[N_max];

int sol[N_max]; // sol[i] == CATE DRUMURI DISTINCTE CU CONSUM MINIM DE ENERGIE EXISTA INTRE PLANETA 1 SI i

int N, M;

void adauga(int x, int y, long double c)
{
    // ADAUGA IN LISTA LUI x PE y

    nr++;
    vf[nr] = y;
    urm[nr] = lst[x];
    cost[nr] = c;
    lst[x] = nr;
}

int main()
{
    int i, x, y, p;

    long double price, c, COST;

    in >> N >> M;

    for(i = 1; i <= M; i++)
    {
        in >> x >> y;

        in >> price;

        c = log10(price);

        adauga(x, y, c);
        adauga(y, x, c);
    }

    for(i = 1; i <= N; i++) d[i] = 2e9;

    // INSEREZ IN COADA NODUL 1
    C.push(1);

    d[1] = 1;
    sol[1] = 1;

    while( !C.empty() )
    {
        x = C.front();
        C.pop();

        // PARCURG VECINII y AI LUI x
        p = lst[x];

        while(p != 0)
        {
            y = vf[p];

            COST = cost[p];

            if( d[x] + COST < d[y] )
            {
                C.push(y);

                d[y] = d[x] + COST;
                sol[y] = sol[x];
            }
            else
                if( fabs(d[x] + COST - d[y]) <= eps )
                {
                    sol[y] += sol[x];

                    sol[y] %= mod;
                }

            p = urm[p];
        }
    }

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

    return 0;
}