#include <fstream>
#include <vector>
#include <queue>
#define Nmax 1505
#define nod first
#define cost second
using namespace std;
ifstream f("dmin.in"); ofstream g("dmin.out");
const int inf = 200000, MOD = 104659;
int N, M, a;
//int v, w;
int cmin[Nmax], nrdr[Nmax];
vector < pair <int, int> > L[Nmax];
queue <int> Q;
void BFS()
{   Q.push(1); cmin[1]=nrdr[1]=1;
    while(!Q.empty())
    {   a=Q.front(); Q.pop();
        vector< pair <int, int> >::iterator it=L[a].begin(), sf=L[a].end();
        for(; it!=sf; ++it)
        {
            //v=(*it).nod;
            //w=(*it).cost;
            if(cmin[a] * (*it).cost < cmin[(*it).nod])
                        {   cmin[(*it).nod] = cmin[a] * (*it).cost;
                            nrdr[(*it).nod] = nrdr[a];
                            Q.push((*it).nod);
                        }
                else
                if(cmin[a] * (*it).cost == cmin[(*it).nod])
                        {   nrdr[(*it).nod] += nrdr[a];
                            if(nrdr[(*it).nod] >= MOD) nrdr[(*it).nod] -= MOD;
                            //Q.push((*it).nod);
                        }
        }
    }
}
int main()
{   f>>N>>M;
    for(int i=2; i<=N; ++i) cmin[i]=inf;
    for(int x, y, c, i=1; i<=M; ++i)
        {   f>>x>>y>>c;
            L[x].push_back(make_pair(y,c));
            L[y].push_back(make_pair(x,c));
        }
    BFS();
    for(int i=2; i<=N; ++i) g<<nrdr[i]<<' ';
    g<<'\n'; g.close();
    return 0;
}