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

using namespace std;
const int NMAX = 1501, //MMAX = 2501,
          MOD = 104659;
const double EPS = 1e-9,
             INF = 1e+9;

struct muchie
{
    int y;
    double w;

};

int N, M;
double D[NMAX]; ///  D[i] = distanta minima de la nodul src la i
int nrD[NMAX];  ///nrD[i] = numarul de drumuri de lungime D[i]
vector<muchie> G[NMAX];
queue<int> Q;
bool inQ[NMAX]; ///inQ[i] = 1 <==> nodul i este in coada

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

void citire()
{
    int x, y, c;
    double w;
    f >> N >> M;
    while(M--)//for(int i = 1; i <= M; ++i)
    {
        f >> x >> y >> c;
        w = log(c);
        G[x].push_back({y, w});
        G[y].push_back({x, w});
    }
}

void init(int src)
{
    for(int i = 1; i <= N; i++)
        D[i] = INF;
    D[src] = 0;
}

void BellmanFord(int src)
{
    int crt, dest;
    double cost;
    init(src);
    Q.push(src);
    inQ[src] = 1;
    nrD[src] = 1;
    while(!Q.empty())
    {
        crt = Q.front();
        Q.pop();
        inQ[crt] = 0;
        for(muchie &m : G[crt])
        {
            cost = D[crt] + m.w;
            dest = m.y;
            if(fabs(cost - D[dest]) <= EPS)
                nrD[dest] = (nrD[dest] + nrD[crt]) % MOD;
            else
                if(D[dest] - cost > EPS)
                {
                    D[dest] = cost;
                    nrD[dest] = nrD[crt];
                    if(inQ[dest] == 0)
                    {
                        Q.push(dest);
                        inQ[dest] = 1;
                    }
                }
        }
    }
}

int main()
{
    citire();
    BellmanFord(1);
    for(int i = 2; i <= N; i++)
        g << nrD[i] << ' ';
    f.close();
    g.close();
    return 0;
}

/**
  Aplicăm algoritmul Bellman-Ford pornind din nodul 1.

  Pe langa vectorul D[] in care retinem distantele minime, vom mai folosi
  un vector nrD[] in care păstrăm pentru fiecare nod i numarul de drumuri de lungime D[i].

  Cand relaxam o muchie vom face update, daca este cazul,
  atat in vectorul D[] cat si in vectorul nrD[].

  Deoarece costul drumurilor a fost definit ca produs de muchii,
  in vectorul D[] putem ajunge sa avem numere foarte mari.

  Pentru a lucra cu valori rezonabile, vom logaritma costul fiecarei muchii intr-o baza oarecare.
  Astfel putem transforma produsul in suma, folosind o proprietate a logaritmilor,
  fapt ce duce la o implementare simpla si rapida, folosind doar date de tip double.
*/