#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <fstream>
#include <utility>
#include <numeric>

using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;

#define MAX 987654321



int main() {
	int N, M;
	ifstream iff("dijkstra.in");
	ofstream off("dijkstra.out");

	iff >> N >> M;
	auto _g = vvii(N + 1, vii());

	for (int i = 0; i < M; ++i) {
		int A, B, C;
		iff >> A >> B >> C;
		_g[A].push_back(make_pair(B, C));
	}

	set<ii> q;
	vector<int> d(N + 1, MAX);
	q.insert(make_pair(1, 0));
	d[1] = 0;
	while (!q.empty()) {
		auto it = q.begin();
		int node = it->first;

		q.erase(it);

		for (auto vecin : _g[node]) {

			int iv = vecin.first;
			int ival = vecin.second;

			int dist = d[node] + ival;

			if (d[iv] > dist) {

				if (d[iv] != MAX) {
					q.erase(make_pair(iv, d[iv]));
				}

				d[iv] = dist;
				q.insert(make_pair(iv, dist));
			}

		}
	}
	
	for (int i = 2; i < d.size(); ++i) {
		if (d[i] == MAX) {
			off << 0 << " ";
		}
		else {
			off << d[i] << " ";
		}
	}
	off << endl;

}