#include     <iostream>
#include     <fstream>
#include     <queue>
#include     <vector>
const int oo = (1 << 30);
const int MAX = 50005;

using namespace std;

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

int n, m;
int d[50005];
bool inCoada[MAX];

struct comparaDistante {
	bool operator()(int  x, int y) {
		return d[x] > d[y];
	}
};

vector < pair < int, int > > G[MAX];

priority_queue < int, vector < int >, comparaDistante> Coada;

void Dijkstra(int nodStart) {
	for (int i = 1; i <= n; i++) d[i] = oo;
	d[nodStart] = 0;
	Coada.push(nodStart);
	inCoada[nodStart] = true;

	while (!Coada.empty()) {
		int nodCurent = Coada.top();
		Coada.pop();
		inCoada[nodCurent] = false;

		for (unsigned int i = 0; i < G[nodCurent].size(); i++) {
			int vecin = G[nodCurent][i].first;
			int cost = G[nodCurent][i].second;
			if (d[nodCurent] + cost < d[vecin]) {
				d[vecin] = d[nodCurent] + cost;
				if (inCoada[vecin] == false) {
					inCoada[vecin] = true;
					Coada.push(vecin);
				}
			}
		}
	}

}

int main()
{
	ios_base::sync_with_stdio(false);
	in.tie(NULL), out.tie(NULL);

	in >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y, c;
		in >> x >> y >> c;
		G[x].push_back(make_pair(y, c));
	}
	Dijkstra(1);

	for (int i = 2; i <= n; i++)
		if (d[i] != oo)
			out << d[i] << ' ';
		else
			out << "0 ";

	return 0;
}