#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<vector>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pii pair<int,double>
#define pb push_back
#define N 1510
#define M 104659
const int inf=200010;
int n,m,X;
vector< pii > a[N];
double d[N];
int h[N],nh,inheap[N];
int nr[N];
inline void citire()
{
	scanf("%d%d",&n,&m);
	X=1;
	int x,y,c;
	double c1;
	for(int i=0; i<m; ++i)
	{
		scanf("%d%d%d",&x,&y,&c);
		c1=log((double)c);
                a[x].pb(mp(y,c1));
		a[y].pb(mp(x,c1));
	}
}
inline int left_son(int x)
{
	return x<<1;
}
inline int right_son(int x)
{
	return (x<<1)+1;
}
inline int father(int x)
{
	return x>>1;
}
inline void upheap(int k)
{
	int key=h[k];
	while(k>1 && d[key]<d[h[father(k)]])
	{
		h[k]=father(k);
		inheap[h[k]]=k;
		k=father(k);
	}
	h[k]=key;
	inheap[h[k]]=k;
}
inline void downheap(int k)
{
	int son;
	do
	{
		son=0;
		if(left_son(k)<=nh)
		{
			son=left_son(k);
			if(right_son(k)<=nh && d[h[right_son(k)]]<d[h[son]])
				son=right_son(k);
			if(d[h[son]]>=d[h[k]])
				son=0;
		}
		if(son)
		{
			swap(h[k],h[son]);
			inheap[h[k]]=k;
			inheap[h[son]]=son;
			k=son;
		}
	}while(son);
}
inline void dijkstra()
{
	for(int i=1; i<=n; ++i)
		d[i]=inf;
        nh=1;
	nr[X]=1;
	h[1]=X;
	inheap[X]=1;
	d[X]=0;
	int next;
	double cost;
	while(nh>0)
	{
		int now=h[1];
		inheap[now]=0;
		h[1]=h[nh--];
		if(nh>0)
		{
			inheap[h[1]]=1;
			downheap(1);
		}
		for(size_t i=0,lim=a[now].size(); i<lim; ++i)
		{
			next=a[now][i].fs;
			cost=a[now][i].sc+d[now];
			if(cost<d[next])
			{
				d[next]=cost;
				nr[next]=nr[now];
				if(inheap[next]!=0)
					upheap(inheap[next]);
				else
				{
					h[++nh]=next;
					inheap[next]=nh;
					upheap(nh);
				}
			}
			else
			if(cost==d[next])
			{
				nr[next]+=nr[now];
				if(nr[next]>=M)
					nr[next]-=M;
			}
		}
	}
}
int main()
{
	freopen("dmin.in","r",stdin);
	freopen("dmin.out","w",stdout);
        citire();
        dijkstra();
        for(int i=2; i<n; ++i)
		printf("%d ",nr[i]);
	printf("%d\n",nr[n]);
	return 0;
}