#include<fstream>
#include<algorithm>
#include<cmath>
using namespace std;
ifstream fin("dmin.in");
ofstream fout("dmin.out");
#define lung 1501
#define eps 1e-101
struct nod{nod *next;
           int val,cost;
};
nod *q,*v[lung];
int n,m,k,h[lung],poz[lung],rasp[lung];
long long d[lung];
inline void upheap(int x)
{int tata;
	while (x > 1)
	{   tata = x >> 1;
	    if (d[h[tata]] > d[h[x]])
		{   poz[h[tata]] = x;
		    poz[h[x]] = tata;
			h[x] = h[x] + h[tata] - (h[tata] = h[x]);
			x= tata;
		}
		else
			x = 1;
	}
}
inline void downheap(int x)
{int fiu;
	while (x >= k)
	{   fiu = x;
	    if ((x<<1) <= k)
		{   fiu = x << 1;
			if (fiu+1 <=k)
				if (d[h[fiu+1]] < d[h[fiu]])
					++fiu;
		}
		else
			break;
		if (d[h[fiu]] < d[h[x]])
		{   poz[h[fiu]] = x;
		    poz[h[x]] = fiu;
			h[x] = h[x] + h[fiu] - (h[fiu] = h[x]);
		    x = fiu;
		}
	}
}
inline void dijkstra()
{int min,i;
 long long a=2;
	for (i=1;i<=61;++i)
		a=a*2;
    for (i=2;i<=n;++i)
	{   d[i] = a;
		poz[i] = -1;
	}
	rasp[1] = h[1] = poz[1] = 1;
	++k;
	while (k)
	{   min = h[1];
	    poz[h[1]] = 1;
		h[1] = h[1] + h[k] - (h[k] = h[1]);
		--k;
		downheap(1);
		q = v[min];
		while (q)
		{   if (d[q->val] > d[min] * q->cost)
		    {   d[q->val] = d[min] * q->cost;
				if (poz[q->val]>0)
					upheap(poz[q->val]);
				else
				{   h[++k] = q->val;
				    poz[h[k]] = k;
					rasp[q->val] = rasp[min];
					upheap(k);
				}
			}
			else
				if (abs(d[q->val]-d[min]-q->cost) <= eps)
					rasp[q->val] = rasp[q->val]+rasp[min];
			q = q -> next;
		}
	}
}
int main()
{int a,b,c,i;
    fin >> n >> m;
    for (i=1;i<=m;++i)
	{   fin >> a >> b >> c;
	    q = new nod;
		q -> next = v[a];
		q -> val = b;
		q -> cost = c;
		v[a] = q;
		q = new nod;
		q -> val = a;
		q -> next = v[b];
		q -> cost = c;
		v[b] = q;
	}
	dijkstra();
	for (i=2;i<=n;++i)
		fout << rasp[i] % 104659 << " ";
	return 0;
}