#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

#define NMAX 50010
#define INF 1 << 30

int cst[NMAX], viz[NMAX], viz_cnt[NMAX], n, m, i;
vector < pair <int, int> > G[NMAX];
queue <int> Q;

void citire();
int bellman_ford();

int main() {
	
	freopen("bellmanford.in", "r", stdin);
	freopen("bellmanford.out", "w", stdout);
	
	citire();
	
	if (!bellman_ford())
		printf("Ciclu negativ!");
	else
		for (i = 2; i <= n; i++)
			printf("%d ", cst[i]);
	
	return 0;
}

int bellman_ford() {
	
	int node, son, cost, i;
	
	for (i = 2; i <= n; i++)
		cst[i] = INF;
	
	Q.push(1), viz[1] = 1, cst[1] = 0;
	while (!Q.empty()) {
		node = Q.front();
		for (i = 0; i < G[node].size(); i++) {
			son = G[node][i].first, cost = G[node][i].second;
			if (cst[node] + cost < cst[son]) {
				cst[son] = cst[node] + cost;
				if (!viz[son]) {
					Q.push(son), viz[son] = 1, viz_cnt[son]++;
					if (viz_cnt[son] > n)
						return 0;
				}
			}
		}
		Q.pop(), viz[node] = 0;
	}
	
	return 1;
}

void citire() {
	
	int x, y, c;
	
	scanf("%d %d", &n, &m);
	for (i = 1; i <= m; i++) {
		scanf("%d %d %d", &x, &y, &c);
		G[x].push_back( make_pair(y, c) );
	}
}