#include <fstream>
#include <queue>
#include <vector>
using namespace std;

typedef pair<int, int> pi;

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

const int INF = 1e9 + 1;
const int MARIME = 100005;

int n, m, start, dist[MARIME];
bool in_coada[MARIME];

priority_queue<pi, vector<pi>, greater<pi>> pq;
vector<pi> graf[MARIME];

int main() {
	// citire si pregatire
	start = 1;
	fin >> n >> m;
	for (int i = 1; i <= n; i++) {
		dist[i] = INF;
	}
	dist[start] = 0;
	pq.push({0, start});
	for (int i = 1; i <= m; i++) {
		int x, y, d;
		fin >> x >> y >> d;
		graf[x].push_back(make_pair(y, d));
	}
	// dijkstra
	while (!pq.empty()) {
		int nod = pq.top().second;
		int cost_nod = pq.top().first;
		pq.pop();

		if (cost_nod > dist[nod]) continue;

		for (auto& x : graf[nod]) {
			int vecin = x.first;
			int cost_muchie = x.second;
			if (dist[nod] + cost_muchie < dist[vecin]) {
				dist[vecin] = dist[nod] + cost_muchie;
				pq.push({dist[vecin], vecin});
			}
		}
	}
	// afisare
	for (int i = 2; i <= n; i++) {
		fout << (dist[i] == INF ? 0 : dist[i]) << ' ';
	}
	return 0;
}