#include <stdio.h>
#include <vector>
using namespace std;

class edge{
	public: int from,to,cost;
	public:edge(){}
	public:edge(int f,int t,int c):from(f),to(t),cost(c){}
};

int n,m;
edge edges[250000];
int dist[50000];
const int INF=50000005;

int main(){
	int x,y,c;
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	
	scanf("%d",&n);scanf("%d",&m);
	for(int i=0;i<m;i++){
		scanf("%d",&x);scanf("%d",&y);scanf("%d",&c);
		edges[i].from=x;edges[i].to=y;edges[i].cost=c;
	}
	
	for(int i=2;i<=n;i++)
		dist[i]=INF;
	dist[0]=0;
	for(int i=1;i<=(n-1);i++){
		for(int j=0;j<m;j++){
			if(dist[edges[j].to]>dist[edges[j].from]+edges[j].cost)
				dist[edges[j].to]=dist[edges[j].from]+edges[j].cost;
		}
	}
	//for(int i=1;i<=(n-1);i++){
	//	for(int j=1;j<=n;j++)
	//		for(int k=0;k<G[j].size();k++){
	//			if(dist[j]+C[j][k]<dist[G[j][k]])
	//				dist[G[j][k]]=dist[j]+C[j][k];
	//		}
	//}
	bool ok=true;
	//for(int j=1;j<=n && ok;j++)
	//	for(int k=0;k<G[j].size();k++){
	//		if(dist[j]+C[j][k]<dist[G[j][k]])
	//			{ok=false;break;}
	//	}
	for(int j=0;j<m;j++){
			if(dist[edges[j].to]>dist[edges[j].from]+edges[j].cost)
				{ok=false;break;}
		}
	if(!ok)
		printf("Ciclu negativ!");
	else
		for(int i=2;i<=n;i++)
			printf("%d ",dist[i]);	
			
	return 0;
}