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

#define nm 50001

using namespace std;

multimap<int, int> L[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;
		L[x].insert(pair<int, int>(y, l));

	}

	fin.close();

}

void solve() {

	int i;

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

	// add to hash
/*	for (i = 2; i <= N; ++i) {
		H.insert(pair<int, int>(INT_MAX, i));
	}	*/

	// 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 (multimap<int, int>::iterator i = L[s.second].begin(); i != L[s.second].end(); ++i) {
			if (D[i->first] > D[s.second] + i->second) {

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

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

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

				D[i->first] = D[s.second] + i->second;
				H.insert(pair<int, int>(D[i->first], i->first));

			}
		}

	}

	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;

}