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

#define nm 50001

using namespace std;

vector<int> V[nm];
vector<int> F[nm];
//multimap<int, int> H;
queue<int> Q;
vector<int> D;
vector<int> I;
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);
		I.push_back(0);
	}

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

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

		// get min
		// pair<int, int> s = *H.begin();
		// H.erase(H.begin());
		int s = Q.front();
		Q.pop();
		I[s] = 0;

		// iterate neighbors
		// for (int i = 0; i < V[s.second].size(); ++i) {
		for (int i = 0; i < V[s].size(); ++i) {
			// if (D[V[s.second][i]] > D[s.second] + F[s.second][i]) {
			if (D[V[s][i]] > D[s] + F[s][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]));
				D[V[s][i]] = D[s] + F[s][i];
				
				if (!I[V[s][i]]) {
					Q.push(V[s][i]);
					I[V[s][i]] = 1;
				}

			}
		}

	}

	// 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;

}