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

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

#define N 1505
#define xx first
#define yy second
#define MOD 104659
#define NEXT (int)(1e9)

typedef double def;
typedef pair <def, int> nod;
typedef pair <nod, int> all;

const def oo = (def)(1e15);
const def er = (def)(1e-6);

vector <nod> g[N];
int f[N], n, m;
bool q[N];
def d[N];
priority_queue <all, vector <all>, greater <all> > H;

int main() {
	fin >> n >> m;
	while (m--) {
		int x, y; def z;
		fin >> x >> y >> z;
		def Z = (z != 1) ? log(z) : 1;
		g[x].push_back (nod (Z, y));
		g[y].push_back (nod (Z, x));
		cout << x << " " << y << " " << Z << "\n";
	}
	fin.close();
	for (int i = 1; i <= n; ++i)
		d[i] = oo;
	H.push(all (nod (0, 1), 1));
	while (H.size()) {
		def crt = H.top().xx.xx; int x = H.top().xx.yy, fr = H.top().yy; H.pop();
		if (d[x] != oo && (d[x] < crt - er || d[x] > crt + er))
			continue;
		if (d[x] == oo) {
			d[x] = crt;
			H.push(all (nod(crt, x), NEXT));
		}
		if (fr != NEXT) {
			f[x] = (f[x] + fr) % MOD; 
			continue;
		}
		for (vector <nod> :: iterator it = g[x].begin(); it != g[x].end(); ++it)
			if (d[(*it).yy] == oo)
				H.push(all (nod (d[x] + (*it).xx, (*it).yy), f[x]));
	}		
	for (int i = 2; i <= n; ++i)
		fout << f[i] << " ";
	fout.close();
}