#include<fstream>
#include<vector>
#define pb push_back
const int inf = 1000000000;
//determine costul minim al unui lant de la nodul 1 la fiecare dintre nodurile 2, 3, ... , N-1, N.
using namespace std;
const int maxn = 60800;
long viz[maxn],n,m,coada[maxn*5],nr[maxn];
struct dat{
	int l,c;
};
vector <dat> a[maxn];



main(){
   freopen("bellmanford.in","r",stdin);
   freopen("bellmanford.out","w",stdout);
  
  int x,y,z;   

scanf("%d %d",&n,&m);
for(int k=0;k<=n;k++)viz[k]=inf;
for(int i=1;i<=m;i++){
scanf("%d %d %d",&x,&y,&z);
dat o;
o.c=z;o.l=y;
a[x].pb(o);
};
int ig=1,sg=1,nod,val,negativ=0;coada[1]=1;viz[1]=0;
while(ig<=sg && negativ==0){
	nod = coada[ig];
	val = viz[nod];
	for(int i=0;i<a[nod].size();i++){
		if(viz[a[nod][i].l]>val+a[nod][i].c){
			coada[++sg]=a[nod][i].l;
			viz[a[nod][i].l]=val+a[nod][i].c;
			nr[a[nod][i].l]++;
			if(nr[a[nod][i].l]==n && viz[a[nod][i].l]<0)negativ=1;
		}
	}
	ig++;
}

//  printf("\n");
if(negativ){
	printf("Ciclu negativ!");
}else
 for(int i=2;i<=n;i++)printf("%d ",viz[i]);
    
  
  
}