#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
#define MAX 50001
#define INF 1000000000
vector <pair<int, int> > lista[MAX];
queue<int> q;
bool ok[MAX];
int n, m, dist[MAX], tata[MAX], relaxari[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;
	}
	dist[s] = 0;
	q.push(s);
	while(!q.empty()){
		i = q.front();
		q.pop();
		relaxari[i]++;
		if(relaxari[i]==n) return 0;
		ok[i] = false;
		for(j=0; j<lista[i].size(); j++){
			y = lista[i][j].first;
			w = lista[i][j].second;
			if(dist[i]+w<dist[y]){
				dist[y] = dist[i]+w;
				if(ok[y]==false){
					ok[y] = true;
					q.push(y);
				}
			}
		}
	}
	return 1;
}