#include <fstream>
#include <cmath>
#include <queue>
#define INF 2000000000
#define NMAX 1501
#define EPSILON 0.0000001

using namespace std;

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

int n, m, nrd[NMAX];
double M[NMAX][NMAX], dmin[NMAX];

queue<int> Q;

void citire()
{
    int a, b, t;
    fin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(i != j) M[i][j] = INF;
    while(m--)
        fin >> a >> b >> t, M[a][b] = M[b][a] = log(t);
}

void bellman_ford(int nod)
{
    Q.push(nod);
    for(int i = 1; i <= n; ++i) dmin[i] = INF;
    dmin[1] = 0;
    nrd[1] = 1;
    while(!Q.empty())
    {
        int x = Q.front();
        Q.pop();
        for(int i = 1; i <= n; ++i){
            if(x != i)
                if(M[x][i] != INF && dmin[i] > dmin[x] + M[x][i] + EPSILON){
                    dmin[i] = dmin[x] + M[x][i];
                    nrd[i] = nrd[x];
                    Q.push(i);
                }
                else if(fabs(dmin[i] - dmin[x] - M[x][i]) < EPSILON && M[x][i] != INF) nrd[i] += nrd[x];
        }
    }
}

int main()
{
    citire();
    bellman_ford(1);
    for(int i = 2; i <= n; i++)
        fout << nrd[i] % 104659 << ' ';
    return 0;
}