#include <iostream>
#include <fstream>
#define inf 250000001

using namespace std;

ifstream in ("bellmanford.in");
ofstream out ("bellmanford.out");

const int N=50001;
const int M=250001;
int lst[N],vf[M],urm[M],cost[M],q[N+3],nr,d[N],st,dr=-1,nrq[N];
bool inq[N];

void adauga (int x, int y, int c)
{
    vf[++nr]=y;
    urm[nr]=lst[x];
    cost[nr]=c;
    lst[x]=nr;
}
void adauga_q(int x)
{

    if (inq[x])
        return;
    if (dr==N)
    {
        dr=0;
    }
    else dr++;
    q[dr]=x;
    inq[x]=true;
    nrq[x]++;
}
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);
    bool t=false;
    while (dr!=st-1)
    {
        if (st==N)
            st=0;
        x=q[st++];
        inq[x]=false;
        for (int p=lst[x];p!=0;p=urm[p])
        {
            y=vf[p];
            c=cost[p];
            if (d[x]+x<d[y])
            {
                d[y]=d[x]+c;
                adauga_q(y);
                if (nrq[y]==n)
                {
                    t=true;
                    break;
                }
            }
        }
        if (t) break;
    }
    if (t)
    {
        out<<"Ciclu negativ!";
    }
    else
    {
        for (int i=2;i<=n;i++)
            out<<d[i]<<' ';
    }
    return 0;
}