#include <fstream>
#include <queue>
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");
struct lista
{
    int y,c;
    lista *urm;
} *g[50010],*p;
queue <int> q;
int use[50010],inf=2000000000,d[50010],n,m,lim=inf,ok;

void bellmanford (int sursa)
{
    int i,nod;
    for (i=1;i<=n;i++)
        d[i]=inf;
    d[sursa]=0;
    use[sursa]=1;
    q.push (sursa);
    while (!q.empty()&&!ok)
    {
        nod=q.front();
        for (p=g[nod];p;p=p->urm)
            if (d[p->y]>d[nod]+p->c)
            {
                d[p->y]=d[nod]+p->c;
                if (d[p->y]<lim)
                {
                    ok=1;
                    return;
                }
                if (!use[p->y])
                {
                    q.push(p->y);
                    use[p->y]=1;
                }
            }
        q.pop();
        use[nod]=0;
    }
}

int main()
{
    int i,x,y,c;
    fin>>n>>m;
    for (i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        p=new lista;
        p->c=c;
        p->y=y;
        p->urm=g[x];
        g[x]=p;
        if (p->c<lim)
            lim=p->c;
    }
    lim*=n;
    bellmanford(1);
    if (ok)
        fout<<"Ciclu negativ!";
    else
        for (i=2;i<=n;i++)
            fout<<d[i]<<' ';
    fout<<'\n';
    fin.close ();
    fout.close ();
    return 0;
}