#include <iostream>
#include <fstream>
#define nrn 1501
#define nrm 25001
#define maxi 999999999
using namespace std;
ifstream f("dmin.in");
ofstream g("dmin.out");
int t[3][2*nrm], viz[nrn], cost[nrn], c[nrm*2], start[nrn],n,m,i,cnt[nrn];
void liste_adiacenta()
{
    int i,x,y,z,k;
    for (i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        t[0][++k]=y; t[1][k]=start[x]; start[x]=k;
        t[0][++k]=x; t[1][k]=start[y]; start[y]=k;
        t[2][k]=t[2][k-1]=z;
    }
}
void ford(int inc)
{
    int i,x,k,pi=1,ps=1;
    for (i=1;i<=n;i++) cost[i]=maxi;
    cost[inc]=1; c[pi]=inc;
    while (ps<=pi)
    {
        k=c[ps];
        viz[k]=0;
        x=start[k];
        while (x)
        {
            if (cost[k]*t[2][x]<cost[t[0][x]])
            {
                cost[t[0][x]]=cost[k]*t[2][x]%104659;
                     cnt[t[0][x]]++;
                if (!viz[t[0][x]])
                    viz[t[0][x]]=1 , c[++pi]=t[0][x];
            }
            else if (cost[k]*t[2][x]==cost[t[0][x]])
            {
                cnt[t[0][x]]++;
                if (!viz[t[0][x]])
                    viz[t[0][x]]=1 , c[++pi]=t[0][x];
            }
            x=t[1][x];
        }
        ps++;
    }
}
int main()
{
    f>>n>>m;
    liste_adiacenta();
    ford(1);
    for (i=2;i<=n;i++)
        g<<cnt[i]<<" ";
    return 0;
}