/*
Bellman-Ford.
*/

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stdio.h>
#include <limits.h>

#define MAXN	50001

using namespace std;

int nr_noduri, nr_muchii;
vector< pair <int, int> > graf[MAXN];
queue<int> coada;
int drum[MAXN];
bool marcat[MAXN];

void drum_min () {
	int i, v;
	for (i = 1; i <= nr_noduri; i++) 
		drum[i] = INT_MAX;

	drum[1] = 0;
	coada.push(1);
	marcat[1] = true;

	while (!coada.empty()) {
		int u = coada.front();
		coada.pop();
		marcat[u] = false;

		for (v = 0; v < graf[u].size(); v++) {
			if (drum[u] + graf[u][v].second < drum[graf[u][v].first]) {
				drum[graf[u][v].first] = drum[u] + graf[u][v].second;
				if (!marcat[graf[u][v].first]) {
					coada.push(graf[u][v].first);
					marcat[graf[u][v].first] = true;
				}
			}
		}
	}
}

int main () {
	freopen("bellmanford.in", "r", stdin);
	freopen("bellmanford.out", "w", stdout);

	int i, x, y, z;
	scanf("%d %d", &nr_noduri, &nr_muchii);
	for (i = 0; i < nr_muchii; i++) {
		scanf("%d %d %d", &x, &y, &z);
		graf[x].push_back(make_pair(y, z));
	}

	drum_min();

	for (i = 2; i <= nr_noduri; i++)
		if (drum[i] < INT_MAX)
			printf("%d ", drum[i]);
		else
			printf("0 ");

	return 0;
}