#include<stdio.h>
#include<math.h>
#define Nm 1501
#define Inf 32000
#define Mod 104659
#define abs(a) ((a)<0?-(a):(a))
int G[Nm][Nm],D[Nm],n;
int Nrd[Nm],M[Nm];
double C[Nm][Nm],Dm[Nm];

void read()
{
    int m,x,y,c;

    freopen("dmin.in","r",stdin);
    scanf("%d%d",&n,&m);
    while(m--)
    {
	scanf("%d%d%d",&x,&y,&c);
	G[x][D[x]]=y;
	G[y][D[y]]=x;
	C[x][D[x]++]=C[y][D[y]++]=log(c);
    }
}

void solve()
{
    int i,x;
    double m;

    Nrd[1]=1;
    for(i=2;i<=n;i++)
	Dm[i]=Inf;

    while(1)
    {
	m=Inf;
	for(i=1;i<=n;i++)
	    if(!M[i] && Dm[i]<m)
	    {
		m=Dm[i];
		x=i;
	    }
	if(m==Inf)
	    break;

	M[x]=1;
	for(i=0;i<D[x];i++)
	    if(Dm[x]+C[x][i]<Dm[G[x][i]])
	    {
		Dm[G[x][i]]=Dm[x]+C[x][i];
		Nrd[G[x][i]]=Nrd[x];
	    }
	    else
		if(Dm[x]+C[x][i]==Dm[G[x][i]])
		{
		    Nrd[G[x][i]]+=Nrd[x];
		    if(Nrd[G[x][i]]>=Mod)
			Nrd[G[x][i]]-=Mod;
		}
    }
}

void write()
{
    int i;

    freopen("dmin.out","w",stdout);
    for(i=2;i<n;i++)
	printf("%d ",Nrd[i]);
    printf("%d\n",Nrd[i]);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}