#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");

const int INF = 0x7fffffff;
const int NMAX = 50000;

int n;
vector <int> graf[NMAX + 1];
vector <int> cost[NMAX + 1];

int d[NMAX + 1];

void citeste() {
	int e, a, b, c;
	f >> n >> e;
	for (int i = 1; i <= e; i++) {
		f >> a >> b >> c;
		graf[a].push_back(b);
		cost[a].push_back(c);
	}
}

void rezolva(int sursa) {
	for (int i = 1; i <= n; i++) d[i] = INF;
	d[sursa] = 0;

	priority_queue < pair <int, int> > pq;
	pq.push(make_pair(0, sursa));

	while (!pq.empty()) {
		pair <int, int> p = pq.top();
		pq.pop();

		int c = (-1) * p.first;
		int nod = p.second;

		int l = graf[nod].size();
		for (int i = 0; i < l; i++) {
			int fiu = graf[nod][i];
			int cost_nou = c + cost[nod][i];
			if (d[fiu] > cost_nou) {
				d[fiu] = cost_nou;
				pq.push(make_pair((-1) * d[fiu], fiu));
			}
		}
	}
}

void scrie() {
	for (int i = 2; i <= n; i++) {
		if (d[i] == INF) d[i] = 0;
		g << d[i] << ' ';
	}
	g << '\n';
}

int main() {
	citeste();
	rezolva(1);
	scrie();
	return 0;
}