#include <iostream>
#include <fstream>
#include <set>
#include <vector>
#define NMAX 50001
#define oo (1 << 30)

using namespace std;

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

vector<pair<int, int> > G[NMAX];
set<pair<int, int> > heap;
int n, d[NMAX];

void dijkstra(int start) {

	int node, where, cost;
	for (int i = 1; i <= n; i++)
		d[i] = oo;
	d[start] = 0;

	heap.insert(make_pair(0, start));
	while (!heap.empty()) {

		node = heap.begin()->second;
		heap.erase(heap.begin());

		for (unsigned int i = 0; i < G[node].size(); i++) {

			where = G[node][i].first;
			cost = G[node][i].second;
			if (d[where] > d[node] + cost) {

				if (d[where] != oo)
					heap.erase(heap.find(make_pair(d[where], where)));
				d[where] = d[node] + cost;
				heap.insert(make_pair(d[where], where));
			}
		}
	}

}

int main() {

	int m, x, y, cost;
	in >> n >> m;
	for (int i = 1; i <= m; i++) {

		in >> x >> y >> cost;
		G[x].push_back(make_pair(y, cost));
	}
	in.close();
	
	dijkstra(1);

	for (int i = 2; i <= n; i++)
		out << ((d[i] == oo) ? 0 : d[i]) << " ";
	out << "\n";
	out.close();

	return 0;
}