#include <fstream>

using namespace std;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
const int N=50001;

const int M=250001;

const int INF=1e9;

int lst[N], vf[M], urm[M], q[N+5], nr, d[N], cst[M], nrq[N], dr=-1, st;
bool inq[N];
void adauga(int x, int y, int c)
{
    vf[++nr]=y;
    cst[nr]=c;
    urm[nr]=lst[x];
    lst[x]=nr;
}

void adauga_q(int x)
{
    if(inq[x])
        return;
    if(dr==N+1)
        dr=0;
    else
        dr++;
    q[dr]=x;
    nrq[x]++;
    inq[x]=true;
}

int main()
{
    int n,m,x,y,c;
    in>>n>>m;
    for(int i=1; i<=m; i++)
    {
        in>>x>>y>>c;
        adauga(x,y,c);
    }
    for(int i=1; i<=n; i++)
        d[i]=INF;
    d[1]=0;
    adauga_q(1);
    while(dr!=st-1)
    {
        x=q[st++];
        if(st==N+2)
        st=0;
        inq[x]=false;
        for(int p=lst[x]; p!=0; p=urm[p])
        {
            y=vf[p];
            c=cst[p];
            if(d[x]+c<d[y])
            {
                d[y]=d[x]+c;
                adauga_q(y);
                if(nrq[y]==n)
                {
                    out<<"Ciclu negativ!";
                    return 0;
                }
            }
        }
    }
    for(int i=2; i<=n; i++)
        out<<d[i]<<" ";
    return 0;

}