#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

#define NMAX 2501
#define INF 1000000000

using namespace std;

vector<pair<int, long long> > adList[NMAX];
int paths[NMAX], inQueue[NMAX];
queue<int> Q;
int n, m;
long long distances[NMAX];

void dmin(){
	Q.push(1);
	inQueue[1] = 1;
	paths[1] = 1;

	while(!Q.empty()){
		int node = Q.front();
		Q.pop();
		//inQueue[node] = 0;

		vector<pair<int, long long> >::iterator it = adList[node].begin();
		while(it != adList[node].end()){
			pair<int, long long> neigh = *it;
			if(distances[neigh.first] > distances[node] + neigh.second){
				distances[neigh.first] = distances[node] + neigh.second;
				paths[neigh.first] = paths[node];
				if(inQueue[neigh.first] == 0){
					Q.push(neigh.first);
					inQueue[neigh.first] = 1;
			}
			}
			else{
				if(distances[neigh.first] == distances[node] + neigh.second){
					paths[neigh.first] += paths[node];
					paths[neigh.first] %= 104659;
				}
			}

			it++;
		}

	}

}

int main(){
	ifstream f("dmin.in");
	ofstream g("dmin.out");

	int x, y, c;

	f >> n >> m;
	for(int i = 0; i < m; i++){
		f >> x >> y >> c;
		adList[x].push_back(make_pair(y, c));
		adList[y].push_back(make_pair(x, c));
	}
	f.close();

	for(int i = 2; i <= n; i++)
		distances[i] = INF;

	dmin();

	for(int i = 2; i <= n; i++)
		g << paths[i] << " ";

	g.close();
	return 0;
}