#include<fstream>
#define inf 1000009
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int coada[50002],pr,ul,nr,n,m,start[50005],t[4][250005],d[50002],viz[50002],k,x,y,c,vmin;
int main()
{
    bool ok=1;
    int i;
    int k=0;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        k++;
        t[0][k]=y;
        t[1][k]=c;
        t[2][k]=start[x];
        start[x]=k;
    }
    for(i=1;i<=n;i++)
    {
        viz[i]=0;
        d[i]=inf;
    }
    d[1]=0;
    coada[1]=1;
    pr=1;ul=1;
    viz[1]=1;
    nr=1;
    while(nr&&ok==1)
    {
        x=coada[pr];
        for(i=start[x];i;i=t[2][i])
        {
            y=t[0][i];
            c=t[1][i];
            t[3][i]++;
            if(t[3][i]==n) ok=0;
            if(d[x]+c<d[y])
            {
                d[y]=d[x]+c;
                if(viz[y]==0)
                {
                    ul++;
                    if(ul>n)
                    {
                        ul=1;
                    }
                    coada[ul]=y;
                    nr++;
                    viz[y]=1;
                }
            }
        }
        pr++;
        if(pr>n)
            pr=1;
        nr--;
        viz[x]=0;
    }
    if(ok==0) fout<<"Ciclu negativ!";
    else
    {
        for(i=2;i<=n;i++)
        {
            if(d[i]==inf) fout<<0<<' ';
            else fout<<d[i]<<' ';
        }
    }

    fin.close();
    fout.close();
    return 0;
}