#include <fstream>
#include <queue>
#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 2e9

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

const def oo = 1e16;

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;
		g[x].push_back (nod (z, y));
		g[y].push_back (nod (z, x));
	}
	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)
			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();
}