#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <utility>

using namespace std;

const int Nmax = 50001;
const int inf = 1 << 30;

vector <pair <int, int> > H, G[Nmax];
int drum[Nmax], poz[Nmax], n, m;

void citire() {
	int i, x, y, z;
	ifstream f("dijkstra.in");
	f >> n >> m;
	for (i = 0; i < m; i++) {
		f >> x >> y >> z;
		G[x].push_back(make_pair(y, z));
	}
}

int tata(int x) {
	return (x - 1) / 2;
}

int fiust(int x) {
	return x * 2 + 1;
}

int fiudr(int x) {
	return x * 2 + 2;
}

void coboara(int p) {
	while (fiudr(p) < H.size()) {
		if (H[p].first > H[fiust(p)].first || H[p].first > H[fiudr(p)].first){
			if (H[fiust(p)].first < H[fiudr(p)].first) {
				swap(H[fiust(p)], H[p]);
				swap(poz[H[p].second], poz[H[fiust(p)].second]);
				p = fiust(p);
			}
			else {
				swap(H[fiudr(p)], H[p]);
				swap(poz[H[p].second], poz[H[fiudr(p)].second]);
				p = fiudr(p);
			}
		}
		else
			break;
	}

	if (fiust(p) < H.size() && H[p].first > H[fiust(p)].first) {
		swap(H[fiust(p)], H[p]);
		swap(poz[H[p].second], poz[H[fiust(p)].second]);
		p = fiust(p);
	}
}

void urca(int p) {
	while (p > 0 && H[tata(p)].first > H[p].first) {
		swap(H[tata(p)], H[p]);
		swap(poz[H[p].second], poz[H[tata(p)].second]);
		p = tata(p);
	}
}

void Dijkstra() {
	int i, k, x, y, viz[Nmax] = { 0 };
	pair <int, int> a;

	for (i = 2; i <= n; i++) {
		drum[i] = inf;
	}
	H.push_back(make_pair(0, 1));
	viz[1] = 1;

	while (!H.empty()) {
		a = H[0];
		H[0] = H[H.size() - 1];
		H.pop_back();
		if (!H.empty())
			coboara(0);
		for (i = 0; i < G[a.second].size(); ++i) {
			y = G[a.second][i].second;		//costul vecinului
			x = G[a.second][i].first;		//vecinul

			if (drum[x] > drum[a.second] + y) {
				drum[x] = drum[a.second] + y;
				if (viz[x] == 0) {
					H.push_back(make_pair(drum[x], x));
					poz[x] = H.size() - 1;
					urca(poz[x]);
				}
				else {
					H[poz[x]].first = drum[x];
					urca(poz[x]);
				}
			}
		}
	}
}

int main() {
	int i;
	citire();
	Dijkstra();
	ofstream g("dijkstra.out");
	for (i = 2; i <= n; ++i) {
		if (drum[i] == inf)
			drum[i] = 0;
		g << drum[i] << " ";
	}
	g.close();
	//getchar();
	return 0;
}