#include<cstdio>
const int N=50000,M=250000,P=20000000;
int m,n,i,k,l,r,d[N],e[7*N],v[N],u[N],*g[N],*h[N],w[N],j,a[M],b[M],c[M],ru=-1,re;
char ra[P];
inline int A()
{
  	int s=0,b=1;
  	ru++;
  	if(ra[ru]==45)
        ru++,b=-1;
  	for(;ra[ru]>47;ru++)
  		s=s*10+ra[ru]-48;
  	return s*b;
}
inline void S(int x)
{
    if(x<0)
        x=-x,ra[re++]=45;
    int i,d=x>999999999?10:x>99999999?9:x>9999999?8:x>999999?7:x>99999?6:x>9999?5:x>999?4:x>99?3:x>9?2:1;
    for(i=d-1;i>=0;x/=10,i--)
        ra[re+i]=x%10+48;
    ra[re+d]=32,re+=d+1;
}
int main()
{
    freopen("bellmanford.in","r",stdin),freopen("bellmanford.out","w",stdout),fread(ra,1,P,stdin),n=A(),m=A();
    for(i=0;i<m;i++)
        a[i]=A(),b[i]=A(),c[i]=A(),a[i]--,b[i]--,w[a[i]]++;
    for(i=0;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[0]=0,v[0]=1,r++;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=1;i<n;i++)
            S(d[i]);
        fwrite(ra,1,re,stdout);
    }
}