#include <iostream>
#include <fstream>

using namespace std;

fstream f,g;

int n,m,i,j,k,l,er;

struct lst
{
    lst *urm;
    int cst,dst;
}*t;

struct nod
{
    char prez;
    lst *p,*u;
    int cst;
}v[50001];

int trk(int i)
{
    v[i].prez=1;
    lst *t;
    for(t=v[i].p->urm;t!=NULL;t=t->urm)
        if(t->cst+v[i].cst<v[t->dst].cst)
        {
            if(v[t->dst].prez==1)
            {
                er=1;
                return 0;
            }
            v[t->dst].cst=t->cst+v[i].cst;
            trk(t->dst);
            if(er==1)return 0;
        }
    v[i].prez=0;
}

int main()
{
    f.open("bellmanford.in",ios_base::in);
    g.open("bellmanford.out",ios_base::out);
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
        v[i].p=new lst;
        v[i].p->urm=NULL;
        v[i].u=v[i].p;
        v[i].cst=2e9;
    }
    v[1].cst=0;
    for(i=1;i<=m;i++)
    {
        f>>j>>k>>l;
        t=new lst;
        t->dst=k;
        t->cst=l;
        t->urm=NULL;
        v[j].u->urm=t;
        v[j].u=t;
    }
    trk(1);
    if(er==1)
    {
        g<<"Ciclu negativ!";
        return 0;
    }
    for(i=2;i<=n;i++)g<<v[i].cst<<' ';
}