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

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

#define N 1505
#define xx first
#define yy second
#define MOD 104659
#define oo 1152921504606846976LL

typedef pair <long long, long long> nod;

vector <nod> g[N];
long long f[N], d[N], n, m, q[N];
priority_queue <nod, vector <nod>, greater <nod> > H; 

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