#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

#define NMax 1505
#define oo (1 << 30)
#define EPS 0.0000000001
#define MOD 104659

vector < pair <int, double> > g[NMax];
int n, m, drumuri[NMax];
bool inCoada[NMax];
double D[NMax];
queue < int > q;

int main()
{
    freopen("dmin.in", "r" , stdin);
    freopen("dmin.out","w", stdout);
    scanf("%d%d", &n , &m);
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        double c;
        scanf("%d%d%lf", &x,&y,&c);
        g[x].push_back(make_pair(y, log10(c)));
        g[y].push_back(make_pair(x, log10(c)));
    }

    for(int i = 2; i <= n; i++)
        D[i] = oo;
;
    drumuri[1] = 1;
    q.push(1);
    inCoada[1] = 1;
    while(!q.empty())
    {
        int nod = q.front();
        q.pop();
        inCoada[nod] = 0;
        for(int i = 0; i < g[nod].size(); i++)
        {
            int vecin = g[nod][i].first;
            double cost = g[nod][i].second;
            if(D[vecin] > D[nod] + cost + EPS)
            {
                D[vecin] = D[nod] + cost;
                drumuri[vecin] = drumuri[nod]%MOD;
                if(!inCoada[vecin])
                {
                    inCoada[vecin] = 1;
                    q.push(vecin);
                }
            }
            else if(abs(D[vecin] - D[nod] - cost) < EPS)
                drumuri[vecin] = (drumuri[vecin]%MOD + drumuri[nod]%MOD) %MOD;
        }
    }
    for(int i = 2; i <= n; i++)
        printf("%d ", drumuri[i]);
}