#include <cassert>
#include <cstring>
#include <cstdio>

#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

#define nod second
#define cost first
#define FORIT(it, v) for (typeof((v).begin()) it = (v).begin(); it != (v).end(); ++it)

const int N = 50005;
const int INF = 0x3f3f3f3f;

int n, m;
int sol[N];
vector <pair <int, int> > graf[N];
priority_queue <pair <int, int>, vector<pair <int, int> >, greater<pair <int, int > > > q;

int main() {
	assert(freopen("dijkstra.in", "r", stdin) != NULL);
	assert(freopen("dijkstra.out", "w", stdout) != NULL);
	
	assert(scanf("%d %d", &n, &m) == 2);
	for (int i = 1; i <= m; ++i) {
		int x, y, z;
		assert(scanf("%d %d %d", &x, &y, &z) == 3);
		graf[x].push_back(make_pair(z, y));
	}
	
	memset(sol, INF, sizeof(sol));
	sol[1] = 0;
	q.push(make_pair(0, 1));
	while (!q.empty()) {
		int nodCurent = q.top().nod;
		int costCurent = q.top().cost;
		q.pop();
		FORIT(it, graf[nodCurent]) {
			costCurent = sol[nodCurent] + it->cost;
			if (costCurent < sol[it->nod]) {
				sol[it->nod] = costCurent;
				q.push(make_pair(costCurent, it->nod));
			}
		}
	}
	
	for (int i = 2; i <= n; ++i)
		printf("%d ", sol[i] != INF ? sol[i]:0);
	
	return 0;
}