#include <iostream>
#include <fstream>
#include <queue>
#include <cmath>
using namespace std;
 
ifstream in("dmin.in");
ofstream out("dmin.out");
 
#define INF 0x3f3f3f3f
#define eps 1e-10
#define mod 104659
 
const int N_max = 1505;
const int M_max = 2505;
 
int vf[2 * M_max];
int urm[2 * M_max];
int lst[N_max];
int nr;
 
bool inC[N_max];
 
long double cost[2 * M_max];
 
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 c, COST;
 
    in >> N >> M;
 
    for(i = 1; i <= M; i++)
    {
        in >> x >> y >> c;
 
        long double Cost = log(c);
 
        adauga(x, y, Cost);
        adauga(y, x, Cost);
    }
 
    for(i = 1; i <= N_max; i++) d[i] = INF;
 
    // INSEREZ IN COADA NODUL 1
    C.push(1);
 
    d[1] = 0;
    sol[1] = 1;
 
    inC[1] = true;
 
    while( !C.empty() )
    {
        x = C.front();
        C.pop();
 
        inC[x] = false;
 
        // PARCURG VECINII y AI LUI x
        p = lst[x];
 
        while(p != 0)
        {
            y = vf[p];
 
            COST = cost[p];
 
            if( fabs(d[x] + COST - d[y]) <= eps )
            {
                sol[y] += sol[x];
 
                if(sol[y] >= mod) sol[y] = sol[y] - mod;
            }
 
            if(d[y] - d[x] - COST > eps)
            {
                d[y] = d[x] + COST;
                sol[y] = sol[x];
 
                if(!inC[y])
                {
                    C.push(y);
                    inC[y] = true;
                }
            }
 
            p = urm[p];
        }
    }
 
    for(i = 2; i <= N; i++) out << sol[i] << " ";
 
    return 0;
}