#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 in_buffer[BUFF_SIZE], out_buffer[BUFF_SIZE];
int in_pos = 0, out_pos = 0;

void read(int& a) {

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

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

inline void putChar(const char &C) {

	out_buffer[out_pos++] = C;
	if (out_pos == BUFF_SIZE) {
		out.write(out_buffer, BUFF_SIZE);
		out_pos = 0;
	}
}

inline void write(int X) {
	
	static char digs[10];
	int n = 0, q;
	do {
		
		q = X / 10;
		digs[n++] = X - (q << 1) - (q << 3) + 48;
		X = q;

	} while (X);

	while (n--) {
		putChar(digs[n]);
	}
	putChar(' ');
}


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++)
		write(((d[i] == oo) ? 0 : d[i]));

	out.write(out_buffer, out_pos);
	out.close();
	return 0;
}