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