#include <fstream>
#include <map>
#include <vector>
#include <limits>

#define nm 50001

using namespace std;

vector<int> V[nm];
vector<int> F[nm];
multimap<int, int> H;
vector<int> D;
int N;

void read() {

	int x, y, l, M;

	ifstream fin("dijkstra.in");
	fin >> N >> M;

	// add edges
	while (M--) {

		fin >> x >> y >> l;
		V[x].push_back(y);
		F[x].push_back(l);

	}

	fin.close();

}

void solve() {

	int i;

	// set initial distances
	for (i = 0; i <= N; ++i) {
		D.push_back(INT_MAX);
	}

	// add initial node
	D[1] = 0;
	H.insert(pair<int, int>(0, 1));

	// put into set
	while (!H.empty()) {

		// get min
		pair<int, int> s = *H.begin();
		H.erase(H.begin());

		// iterate neighbors
		for (int i = 0; i < V[s.second].size(); ++i) {
			if (D[V[s.second][i]] > D[s.second] + F[s.second][i]) {

				multimap<int, int>::iterator lo = H.lower_bound(D[V[s.second][i]]), hi = H.upper_bound(D[V[s.second][i]]), rm = H.end();

				// get old
				for (multimap<int, int>::iterator j = lo; j != hi; ++j) {
					if (j->second == V[s.second][i]) {
						rm = j;
						break;
					}
				}

				// erase old
				if (rm != H.end()) {
					H.erase(rm);
				}

				// put new
				D[V[s.second][i]] = D[s.second] + F[s.second][i];
				H.insert(pair<int, int>(D[V[s.second][i]], V[s.second][i]));

			}
		}

	}

	// set zero
	for (i = 2; i <= N; ++i) {
		if (D[i] == INT_MAX) {
			D[i] = 0;
		}
	}

}

void write() {

	int i;

	ofstream fout("dijkstra.out");

	// write dists
	for (i = 2; i <= N; ++i) {
		fout << D[i] << ' ';
	}

	fout << '\n';
	fout.close();

}

int main() {

	read();
	solve();
	write();

	return 0;

}