#include <fstream>
#include <queue>
#include <cmath>
#include <iostream>
using namespace std;

ifstream fin ("dmin.in");
ofstream fout ("dmin.out");

const double oo = (double)(1e13);

#define N 1505
#define xx first
#define yy second
#define MOD 104659

typedef pair <double, int> nod;

vector <nod> g[N];
int f[N], n, m;
bool q[N];
double d[N];
queue <int> Q;

int main() {
	fin >> n >> m;
	while (m--) {
		int x, y; double z;
		fin >> x >> y >> z;
		g[x].push_back (nod (z, y));
		g[y].push_back (nod (z, x));
	}
	for (int i = 2; i <= n; ++i)
		d[i] = oo;
	fin.close();
	Q.push(1);
	f[1] = 1;
	q[1] = 1;
	while (Q.size()) {
		int x = Q.front(); Q.pop();
		q[x] = 0;
		for (vector <nod> :: iterator it = g[x].begin(); it != g[x].end(); ++it) {
			int NEW = d[x] + (*it).xx;
			if (NEW < d[(*it).yy]) {
				d[(*it).yy] = NEW;
				f[(*it).yy] = f[x];
				if (!q[(*it).yy]) {
					q[(*it).yy] = 1;
					Q.push((*it).yy);
				}
				continue;
			}
			if (NEW == d[(*it).yy])
				f[(*it).yy] = (f[(*it).yy] + f[x]) % MOD;
		}
	}	
	for (int i = 2; i <= n; ++i)
		fout << f[i] << " ";
	fout.close();
}