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

#define MAX 50001
#define INF 0x3f3f3f3

using std::vector;
using std::queue;

struct node{
	int end,cost;
};

int n,m,dist[MAX],pred[MAX];
bool neg_cycle;

vector<node>graph[MAX];
int main(){
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	
	scanf("%d %d",&n,&m);
	for(int i=0;i<m;++i){
		int x,y,z;
		scanf("%d %d %d",&x,&y,&z);
		node tmp;
		tmp.end=y;
		tmp.cost=z;
		graph[x].push_back(tmp);
	}
	
	memset(dist,INF,n+1);

	dist[1]=0;

	for(int i=1;i<=n;++i){
		for(auto j:graph[i]){
			if(dist[j.end]> dist[i]+j.cost){
				dist[j.end] = dist[i]+j.cost;
				pred[j.end]=i;
			}
		}	
	}

	for(int i=1;1<=n;++i){
		for(auto j:graph[i]){
			if(dist[i]+j.cost <	dist[j.end]){
				neg_cycle=false;
				break;			
			}
		}
	}

	if(neg_cycle){
		printf("Ciclu negativ!");
	}else{
		for(int i=2;i<=n;++i){
			printf("%d ",dist[i]);
		}
	}
	return 0;
}