#include<fstream>
#include<cmath>
#define pb push_back 
#define mp make_pair
#include<vector>
#define fi first
#define se second
#define NM 1510
#define mod 104659
#define inf 1<<30
#define eps 0.000001
using namespace std;
ifstream f("dmin.in");
ofstream g("dmin.out");
vector<pair<int,double> > v[NM];
int x,y,n,m,i,A[NM],d,H[NM],L,P[NM];
double c,D[NM];
double ab(double x){if(x<0) return -x; return x;}
void urca(int po)
{
    while(po&&D[H[po]]<D[H[po>>1]])
    {
        swap(H[po],H[po>>1]);
        swap(P[H[po]],P[H[po>>1]]);
        po>>=1;
    }
}
void coboara(int po){
    int y=0;
    while(po!=y){
        y=po;
        if((y<<1)<=L&&D[H[y<<1]]<D[H[po]])
            po=y<<1;
        if((y<<1)+1<=L&&D[H[(y<<1)+1]]<D[H[po]])
            po=(y<<1)+1;
        swap(H[po],H[y]);
        swap(P[H[po]],P[H[y]]);
    }
}
int main ()
{
	f>>n>>m;
	for(i=1;i<=m;++i)
	{
		f>>x>>y>>c;
		v[x].pb(mp(y,log(c)));
		v[y].pb(mp(x,log(c)));
	}
	for(i=2;i<=n;++i)
		D[i]=inf;
	H[++L]=1;
	P[1]=1;
	A[1]=1;
	while(L)
	{
		x=H[1];
		H[1]=H[L--];
		coboara(1);
		for(i=0;i<v[x].size();++i)
		{
			d=v[x][i].fi;
			c=v[x][i].se;
			if(ab(D[x]+c-D[d])>eps&&D[x]+c<D[d])
			{
				D[d]=D[x]+c;
				A[d]=A[x];
				if(!P[d])
				{
					H[++L]=d;
					P[d]=L;
					urca(L);
				}
				else
					urca(P[d]);
			}
			else
			if(ab(D[x]+c-D[d])<=eps)
			{
				A[d]+=A[x];
				if(A[d]>=mod)
					A[d]-=mod;
			}
		}
	}
	for(i=2;i<=n;++i)
		g<<A[i]<<" ";
	return 0;
}