#include<stdio.h>
#include<stdlib.h>
int m,n,i,j,k,l,r,p,d[50001],e[1500000],*g[50001],*h[50001],w[50001],a[250001],b[250001],c[250001],v[50001],u[50001];
int main() {
	freopen("bellmanford.in","r",stdin),freopen("bellmanford.out","w",stdout),scanf("%d%d",&n,&m);
	for(i=2;i<=n;i++)
     	d[i]=50001;
	for(i=1;i<=m;i++)
     	scanf("%d%d%d",&a[i],&b[i],&c[i]),w[a[i]]++;
    for(i=1;i<=n;w[i++]=0)
        g[i]=(int*)malloc(w[i]*sizeof(int)),h[i]=(int*)malloc(w[i]*sizeof(int));
    for(i=1;i<=m;i++)
        g[a[i]][w[a[i]]]=b[i],h[a[i]][w[a[i]]++]=c[i];
	for(e[r++]=v[1]=1;l<r&&!k;)
    for(j=e[l++],v[j]=i=0;i<w[j];i++)
    if(d[g[j][i]]>d[j]+h[j][i]) {
        d[g[j][i]]=d[j]+h[j][i];
        if(!v[g[j][i]])
            if(u[g[j][i]]>n)
                k=1;
            else
                e[r++]=h[j][i],v[g[j][i]]=1,u[g[j][i]]++;
    }
    if(k)
        printf("Ciclu negativ!");
    else
        for(i=2;i<=n;i++)
            printf("%d ",d[i]);
}