#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

const int N = 1 + 5e4, inf = 0x3f3f3f3f;

struct Node{
	int y, c;
	Node(int y, int c) : y(y), c(c) {}
};

class SmartHeap{
	int *val, H[N], loc[N];

	inline void swp(int x, int y){
		swap(H[x], H[y]);
		loc[ H[x] ] = x;
		loc[ H[y] ] = y;
	}
	inline bool better(int x, int y){
		return val[ H[x] ] < val[ H[y] ];
	}
public:
	SmartHeap(int* val) : val(val) {
		memset(loc, 0, sizeof(loc));
		H[0] = 0;
	}
	inline bool empty(){
		return H[0] == 0;
	}
	void push(int x, int v){
		if (val[x] <= v)
			return;
		val[x] = v;
		if ( !loc[x] ){
			H[ ++H[0] ] = x;
			loc[x] = H[0];
		}
		for (x = loc[x]; x > 1 && better(x, x >> 1); x >>= 1)
			swp(x, x >> 1);
	}
	int pop(){
		int x = 1, m = 1;
		swp(1, H[0]);
		loc[ H[H[0]] ] = 0;

		do {
			x = m;
			if ( 2 * x < H[0] && better(2 * x, m) )
				m = 2 * x;
			if ( 2 * x + 1 < H[0] && better(2 * x + 1, m ) )
				m = 2 * x + 1;
			swp(m, x);
		} while (m != x);
		return H[ H[0]-- ];
	}
};

vector<Node> graph[N];
int dist[N], n;

void dijkstra(int x){
	memset(dist, inf, sizeof(dist));
	SmartHeap H(dist);
	H.push(x, 0);

	while ( !H.empty() ){
		x = H.pop();
		for (Node e : graph[x])
			H.push(e.y, dist[x] + e.c);
	}
}

int main(){
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	int m, x, y, c;

	cin >> n >> m;
	while (m--){
		cin >> x >> y >> c;
		graph[x].push_back( Node(y, c) );
	}
	dijkstra(1);

	for (int i = 2; i <= n; i++)
		cout << (dist[i] != inf ? dist[i] : 0) << ' ';
	cout << '\n';

	return 0;
}