#include <cstdio>
#include <vector>
using namespace std;
#define MAX 50001
#define INF 1000000000
vector <pair<int, int> > lista[MAX];
bool ok[MAX];
int n, m, dist[MAX], tata[MAX];
int bellman(int s);
int main()
{
	int i, x, y, w;
	freopen("bellmanford.in", "r", stdin);
	freopen("bellmanford.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(i=1; i<=m; i++){
		scanf("%d%d%d", &x, &y, &w);
		lista[x].push_back(make_pair(y, w));
	}
	if(bellman(1)==0)
		printf("Ciclu negativ!\n");
	else
		for(i=2; i<=n; i++)
			printf("%d ", dist[i]);
	return 0;
}
int bellman(int s)
{
	int i, gata, iter=0, j, y, w;
	for(i=1; i<=n; i++){
		dist[i] = INF;
		tata[i] = 0;
		ok[i] = true;
	}
	dist[s] = 0;
	do{
		gata = 1;
		iter++;
		for(i=1; i<=n; i++)
			if(ok[i]){
				ok[i] = false;
				for(j=0; j<lista[i].size(); j++){
					y = lista[i][j].first;
					w = lista[i][j].second;
					if(dist[i]==INF) continue;
					if(dist[i]+w<dist[y]){
						gata = 0;
						dist[y] = dist[i]+w;
						ok[y] = true;
					}
				}
			}
	}
	while(iter<n and !gata);
	if(iter==n and !gata) return 0;
	return 1;
}