#include <cstdio>
#include <queue>

using namespace std;
char buff[1000000];
int lung=1,poz,ls[50001],urm[250001],vft,exist[50001],d[50001];//vectori ca sa fie bine la programel
struct abc
{
     int nod,c;
} vf[250001];
int read()
{
    int x=0,sgn=1;
    while((buff[poz]<'0'||buff[poz]>'9')&&buff[poz]!='-')
    {
        if(++poz==lung)
        {
            lung=fread(buff,1,1000000,stdin);
            poz=0;
        }

    }
    if(buff[poz]=='-'){sgn=-1;poz++;}
    if(poz==lung)
        {
            lung=fread(buff,1,1000000,stdin);
            poz=0;
        }
    while((buff[poz]>='0'&&buff[poz]<='9')||buff[poz]=='-')
    {
         x=x*10+buff[poz]-'0';
        if(++poz==lung)
        {
            lung=fread(buff,1,1000000,stdin);
            poz=0;
        }
    }
    return x*sgn;

}

void add(int a,int b, int c)
{
    vft++;
    vf[vft].nod=b;
    vf[vft].c=c;
    urm[vft]=ls[a];
    ls[a]=vft;
}
#define inf 2134567890
int main()
{
    queue<int>q;
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    int n,m,i,j,k,c,marime,p,nodul,ok=1,t;
    n=read();t=n;
    m=read();
    for(i=0; i<m; i++)
    {
        j=read();
        k=read();
        c=read();

        add(j,k,c);
    }
    q.push(1);
    for(i=2; i<=n; i++)d[i]=inf;
    d[1]=0;
    exist[1]=1;
 A:   for(i=1; i<n; i++)
   {
        marime=q.size();

        for(j=0; j<marime; j++)
        {
            k=q.front();
            p=ls[k];
            c=0;

            while(p)
            {
                nodul=vf[p].nod;
                if(vf[p].c+d[k]<d[nodul])
                {
                    d[nodul]=vf[p].c+d[k];
                    if(exist[nodul]==0)
                        {
                        q.push(nodul);
                        exist[nodul]=1;

                        } c=1;
                }
                p=urm[p];
            }
            if(c==0)exist[k]=0;
            else q.push(k);
            q.pop();


        }
    }
    if(ok)
{n=2;ok=0;goto A;}
if(!q.empty())printf("Ciclu negativ!");else{n=t;
for(i=2;i<=n;i++)
    printf("%d ",d[i]);}



    return 0;
}