#include <stdio.h>
#define MAX 50001
const int legn=1 << 30;

struct adat{
int a,b,c;
adat *next;
adat(){next=0;}
};

adat *p;
int n,m,l[MAX];

void add(int a,int b,int c){
adat *q=new adat;
q->a=a;
q->b=b;
q->c=c;
q->next=p;
p=q;
}

int b_f(){
int i,count=0;
bool jo=1;
adat *q;
for(i=2;i<=n;i++)l[i]=legn;
l[1]=0;

while((jo)&&(count<n)){
jo=0;

for(q=p;q!=0;q=q->next)
if(l[q->a]+q->c<l[q->b]){
jo=1;
l[q->b]=l[q->a]+q->c;
}

count++;
}

if(count==n){
printf("Ciclu negativ!");
return 0;
}else return 1;

}

int main(){
freopen("bellmanford.in","r",stdin);
freopen("bellmanford.out","w",stdout);
	int i,temp1,temp2,temp3;
scanf("%d %d",&n,&m);

for(i=1;i<=m;i++){
scanf("%d %d %d",&temp1,&temp2,&temp3);
add(temp1,temp2,temp3);
}

temp1=b_f();

if(temp1)
for(i=2;i<=n;i++){
if(l[i]==legn)l[i]=0;
printf("%d ",l[i]);
}



return 0;
}