#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

#define MAXN 1501
#define MOD 104659
#define INF 9.0e15
struct node {
	int key;
	double cost;
	node *next;
};

const double eps = 1.0e-10;

int n, m, pathCount[MAXN];
node *gr[MAXN];
unsigned short heap[MAXN], posInHeap[MAXN], heapSize;
double dist[MAXN];

void minHeapify(int pos);
int extractMin();
void keyDecreased(int pos);
void insert(int key);

void read();
void solve();
inline void add(int a, int b, int cost)
{
	double lgCost;
	node *q = (node *) malloc(sizeof(node));
	q->key = a;
	q->next = gr[b];
	q->cost = lgCost = log10((double)cost);
	gr[b] = q;
	
	q = (node *) malloc(sizeof(node));
	q->key = b;
	q->cost = lgCost;
	q->next = gr[a];
	gr[a] = q;
}

int main()
{
	read();
	solve();
	
	freopen("dmin.out", "w", stdout);
	for (int i = 2 ; i < n ; ++i)
		printf("%d ", pathCount[i]);
	printf("%d\n", pathCount[n]);
	
	return 0;
}

void read()
{
	freopen("dmin.in", "r", stdin);
	scanf("%d%d", &n, &m);
	
	for (int i = 1 ; i <= m ; ++i)
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		add(a, b, c);
	}
}

void minHeapify(int pos)
{
	int smallest = pos;
	
	if ((pos << 1) <= heapSize && dist[heap[(pos << 1)]] < dist[heap[smallest]])
		smallest = pos << 1;
	if ((pos << 1) + 1 <= heapSize && dist[heap[(pos << 1) + 1]] < dist[heap[smallest]])
		smallest = (pos << 1) + 1;
	if (smallest != pos)
	{
		int aux = posInHeap[heap[pos]];
		posInHeap[heap[pos]] = posInHeap[heap[smallest]];
		posInHeap[heap[smallest]] = aux;
		
		aux = heap[pos];
		heap[pos] = heap[smallest];
		heap[smallest] = aux;
		
		minHeapify(smallest);
	}
}

int extractMin()
{
	int result = heap[1];
	heap[1] = heap[heapSize--];
	minHeapify(1);
	return result;
}

void keyDecreased(int pos)
{
	while (pos > 1 && dist[heap[pos]] < dist[heap[pos >> 1]])
	{
		int aux = posInHeap[heap[pos]];
		posInHeap[heap[pos]] = posInHeap[heap[pos >> 1]];
		posInHeap[heap[pos >> 1]] = aux;
	
		aux = heap[pos];
		heap[pos] = heap[pos >> 1];
		heap[pos >> 1] = aux;
		 
		pos >>= 1;
	}
}

void insert(int key)
{
	heap[++heapSize] = key;
	posInHeap[key] = heapSize;
	keyDecreased(heapSize);
}

void solve()
{
	for (int i = 2 ; i <= n ; ++i)
		dist[i] = INF;
		
	dist[1] = 0;
	insert(1);posInHeap[1] = 1;
	pathCount[1] = 1;
	
	while (heapSize > 0)
	{
		int nd = extractMin();
		node *q = gr[nd];
		while (q)
		{
			if (dist[q->key] - dist[nd] - q->cost > eps)
			{
				dist[q->key] = dist[nd] + q->cost;
				pathCount[q->key] = pathCount[nd];
				
				if (posInHeap[q->key] == 0)
					insert(q->key);
				else
					keyDecreased(posInHeap[q->key]);
			}
			else if ((dist[q->key] - dist[nd] - q->cost) < eps && (dist[q->key] - dist[nd] - q->cost) > -eps)
			{
				pathCount[q->key] += pathCount[nd];
				if (pathCount[q->key] >= MOD)
					pathCount[q->key] %= MOD;
			}
			
			q = q->next;
		}
	}
}