#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

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

const int MOD = 104659;
const int N = 1505;
const int M = 2505;
const long double INF = 2000000000.0;
const long double EPS = 0.0000000001;

int n,m,nr,vf[2*M],lst[2*M],urm[2*M],inq[N],q[N+1],cate[N],st,dr;
long double cst[2*M],d[N];

void Adauga(int x,int y, double z)
{
    vf[++nr] = y;
    urm[nr] = lst[x];
    lst[x] =  nr;
    cst[nr] = z;
}

void inc(int &x)
{
    x++;
    if (x == N+1) x = 0;
}


void bf(int nod)
{
    for (int i=1; i<=n; i++) d[i] = INF;
    int x,y;
    long double z;
    st = 0;
    dr = -1;
    inc(dr);
    q[dr] = nod;
    d[nod] = 0;
    inq[dr] = 1;

    while (dr != st - 1)
    {
        x = q[st];
        inc(st);
        for (int p=lst[x]; p!=0; p = urm[p])
        {
            y  = vf[p];
            z = cst[p];
            if (abs(d[y] - d[x] - z) <= EPS)
            {
                cate[y] += cate[x];
                cate[y] %= MOD;
            }
            else if (d[x] + z < d[y])
            {
                d[y] = d[x] + z;
                cate[y] = cate[x];
                ///if (x == 1) cout << cate[1];
                if (!inq[y])
                {
                    inq[y] = 1;
                    inc(dr);
                    q[dr] = y;
                }
            }
        }
    }
}

int main()
{
    in >> n >> m;
    for (int i=1,x,y,z; i<=m; i++)
    {
        in >> x >> y >> z;
        long double val = log10(z);
        ///cout << val << "\n";
        Adauga(x,y,val);
        Adauga(y,x,val);
    }
    cate[1] = 1;
    bf(1);
    for (int i=2; i<=n; i++)
    {
        out << cate[i] << " ";
    }
    return 0;
}