#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<deque>
#define MAX 1505
#define mod 104659
using namespace std;
int n,i,j,k,x,y,a,b,m,cost[MAX],rez[MAX];
vector<pair<int,int> >v[MAX];
bool viz[MAX];
deque<int>c;
struct nod
{
	int poz;
	int cos;
}s[MAX];

void dijkstra(int x)
{
	c.push_back(x);
	viz[x]=true;
	while (!c.empty())
	{
		x=c.front();
		for (j=0;j<v[x].size();j++) 
		{
			a=v[x][j].first;
			b=v[x][j].second;
			if (!viz[a]) cost[a]=cost[x]+b,viz[a]=true,c.push_back(a);else
				 if (cost[a]>cost[x]+b) cost[a]=cost[x]+b,c.push_back(a);
		}
		c.pop_front();
	}
}
int cmp(const nod x,const nod y)
{
	return x.cos<y.cos;
}

int main()
{
	freopen("dmin.in","r",stdin);
	freopen("dmin.out","w",stdout);
	scanf("%d %d",&n,&m);
	for (i=1;i<=m;i++) 
		scanf("%d %d %d",&a,&b,&k),v[a].push_back(make_pair(b,k)),v[b].push_back(make_pair(a,k));
	dijkstra(1);
	for (i=2;i<=n;i++) s[i].poz=i,s[i].cos=cost[i];
	sort(s+1+2,s+n+1,cmp);
	c.push_back(1);
	memset(viz,false,sizeof(viz));
	s[1].poz=1;
	rez[1]=1;
	for (i=1;i<=n;i++)
	{
		x=s[i].poz;
		for (j=0;j<v[x].size();j++)
		{
			a=v[x][j].first;
			b=v[x][j].second;
			if (a!=1 && !viz[a])
			{
				viz[x]=true;
				if (b+cost[x]==cost[a]) rez[a]=(rez[a]+rez[x])%mod;
			}
		}
	}
	for (j=2;j<=n;j++) printf("%d ",rez[j]);
	return 0;
}