#include <fstream>
#include <vector>
#include <climits>

using namespace std;

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

int main()
{
	int n, m, v1, v2, val, *v, *m1, *m2;
	vector<int> *g, *g_val;
	fin >> n >> m;
	v = new int[n + 1];
	g = new vector<int>[n + 1];
	g_val = new vector<int>[n + 1];
	m1 = new int[m];
	m2 = new int[m];
	for (int i = 1; i <= n; ++i) {
		v[i] = INT_MAX;
	}
	while (m--) {
		fin >> v1 >> v2 >> val;
		g[v1].push_back(v2);
		g_val[v1].push_back(val);
	}
	v[1] = 0;
	m1[0] = 1;
	for (int size1 = 1, size2 = 0, *aux; size1 > 0; aux = m1, m1 = m2, m2 = aux, size1 = size2, size2 = 0) {
		for (int i = 0; i < size1; ++i) {
			int node = m1[i];
			for (int j = 0; j < g[node].size(); ++j) {
				int node2 = g[node][j], val = v[node] + g_val[node][j];
				if (v[node2] > val) {
					v[node2] = val;
					m2[size2++] = node2;
				}
			}
		}
	}
	for (int i = 2; i <= n; ++i) {
		fout << (v[i] == INT_MAX ? 0 : v[i]) << " ";
	}
}