#include<cstdio>
#include<vector>
#include<queue>
#define inf 1<<30
using namespace std;
FILE *in = fopen("bellmanford.in", "r"), *out = fopen("bellmanford.out", "w");

vector <int> arc[50001], cost[50001], dist;
queue <int> q;
int n, m;

int main(){
	fscanf (in, "%d %d", &n, &m);
	int i, j, x, y, c, count;
	for (i = 1; i <= m; i++){
		fscanf (in, "%d %d %d", &x, &y, &c);
		arc[x].push_back(y);
		cost[x].push_back(c);
	}
	
	for (i = 0; i <= n; i++) dist.push_back(inf);
	dist[1] = 0; q.push(1); count = n * (n-1);
	
	while (!q.empty() && count--){
	i = q.front(); q.pop();
		for (j = 0; j < (int)arc[i].size(); j++)
			if (dist[arc[i][j]] > dist[i] + cost[i][j]){
				dist[arc[i][j]] = dist[i] + cost[i][j];
				q.push(arc[i][j]);
			}
	}
	
	if (!q.empty()) fprintf(out, "Ciclu negativ!");
	else for (i = 2; i <=n; i++) fprintf(out, "%d ", dist[i]);
	return 0;
}