#include <cstdio>
#include <cmath>
#include <vector>
#include <set>
using namespace std;
#define nmax 1510
#define inf 1<<30
#define eps 0.000001
#define mp make_pair
#define mod 104659

vector <pair <int, double> > g[nmax];
set <pair <double, int> > t;
int n, m, p[nmax];
double d[nmax];

void dijkstra()
{
	int i, x;
	double val;
	for (i=1; i<=n; i++) d[i]=inf;
	t.insert(mp(0,1));
	p[1]=1;
	while (t.size())
	{
		val=(*t.begin()).first;
		x=(*t.begin()).second;
		t.erase(*t.begin());
		for (i=0; i<g[x].size(); i++)
		{
			if (fabs(d[g[x][i].first]-val-g[x][i].second)<eps) p[g[x][i].first]=(p[g[x][i].first]+p[x])%mod; else
			if (val+g[x][i].second<d[g[x][i].first])
			{
				d[g[x][i].first]=val+g[x][i].second;
				p[g[x][i].first]=p[x];
				t.insert(mp(d[g[x][i].first], g[x][i].first));
			}
		}
	}
}
	

int main()
{
	freopen("dmin.in","r",stdin);
	freopen("dmin.out","w",stdout);
	scanf("%d %d",&n,&m);
	int i, x, y, c;
	for (i=1; i<=m; i++) 
	{
		scanf("%d %d %d",&x,&y,&c);
		g[x].push_back(mp(y, log((double) (c))));
		g[y].push_back(mp(x, log((double) (c))));
	}
	dijkstra();
	for (i=2; i<=n; i++) printf("%d ",p[i]);
}