#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);
    }
}

int smaller(double x, double y)
{
    return y-x>0.000001;
}

int equal(double x, double y)
{
    return abs(x-y)<0.000001;
}

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(smaller(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(equal(Dm[x]+C[x][i],Dm[G[x][i]]))
		    Nrd[G[x][i]]=(Nrd[G[x][i]]+Nrd[x])%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;
}