#include <fstream>
#include <cstring>
using namespace std;

constexpr int kMaxN = 50000;
constexpr int kMaxM = 250000;
constexpr int NIL = -1;

struct Edge {
	int v, weight;
	int next;
} G[kMaxM];

int head[kMaxN];
int dist[kMaxN];
bool in_stack[kMaxN];

void df(const int node) {
	in_stack[node] = true;
	for (int i = head[node]; i != NIL; i = G[i].next) {
		const int adj_node = G[i].v;
		if (dist[adj_node] > dist[node] + G[i].weight) {
			dist[adj_node] = dist[node] + G[i].weight;
			if (not in_stack[adj_node]) {
				df(adj_node);
			}
		}
	}
	in_stack[node] = false;
}

int main() {
	ifstream cin("dijkstra.in");
	ofstream cout("dijkstra.out");
	int n, m; cin >> n >> m;
	
	memset(head, NIL, 4 * n);
	for (int i = 0; i < m; i += 1) {
		int u, v, weight; cin >> u >> v >> weight;
		G[i].v = v - 1;
		G[i].weight = weight;
		G[i].next = head[u - 1];
		head[u - 1] = i;
	}
	
	memset(dist + 1, 0x3f, 4 * (n - 1));
	df(0);
	
	for (int i = 1; i < n; i += 1) {
		cout << (dist[i] & -(dist[i] != 0x3f3f3f3f)) << " \n"[i == n - 1];
	}
	return 0;
}