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

vector< vector<int> >G(50005);
vector< vector<int> >C(50005);

int n,m;
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);
		G[x].push_back(y);C[x].push_back(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=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;}
		}
	if(!ok)
		printf("Ciclu negativ!");
	else
		for(int i=2;i<=n;i++)
			printf("%d ",dist[i]);	
			
	return 0;
}