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

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];

char buffer[BUFF_SIZE];
int pos = 0;

void read(int& a) {

	while (!isdigit(buffer[pos]))
		if (++pos == BUFF_SIZE)
			in.read(buffer, BUFF_SIZE), pos = 0;
	a = 0;
	while (isdigit(buffer[pos])) {

		a = a * 10 + (buffer[pos] - '0');
		if (++pos == BUFF_SIZE)
			in.read(buffer, BUFF_SIZE), pos = 0;
	}
}

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;
	read(n), read(m);
	for (int i = 1; i <= m; i++) {

		read(x), read(y), read(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;
}