#include <fstream>
#include <queue>
#include <algorithm>
#include <vector>

using namespace std;

ifstream r("dijkstra.in");
ofstream w("dijkstra.out");

const int n_max = 50001;
const int m_max = 250001;
const int inf = 0x3f3f3f3f;
int d[n_max], cd[8 * n_max];
queue <int> q;
bool viz[n_max];
vector <pair <int, int> > g[n_max];
vector <pair<int, int> > ::iterator it;
int n, m;

void read() {
	int i, j, k, c;
	r >> n >> m;
	for (k = 0; k<m; k++) {
		r >> i >> j >> c;
		g[i].push_back(make_pair(j, c));
	}
}

void dijkstra(int x) {
	int p, prec;
	for (int i = 1; i <= n; i++)
		d[i] = inf;
	d[x] = 0;
	q.push(x);
	viz[x] = true;
	while (!q.empty()) {
		prec = q.front();
		q.pop();
		viz[prec] = false;
		for (it = g[prec].begin(); it != g[prec].end(); it++)
			if (d[prec] + (*it).second<d[(*it).first]) {
				d[(*it).first] = d[prec] + (*it).second;
				if (!viz[(*it).first]) {
					viz[(*it).first] = true;
					q.push((*it).first);
				}

			}
	}
}

int main() {
	read();
	dijkstra(1);
	for (int i = 2; i <= n; i++)
		if (d[i]<inf)
			w << d[i] << " ";
		else
			w << 0 << " ";
	r.close();
	w.close();
	return 0;
}