#include <iostream>
#include <fstream>

using namespace std;

fstream f,g;

int n,m,i,j,k,l,er,h,coada[50001];

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

struct nod
{
    char prez,verif;
    lst *p,*u;
    int cst,orig;
}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;
            if(v[t->dst].verif==0)
            {
                trk(t->dst);
                if(er==1)return 0;
            }
            else if(v[t->dst].orig==0)
            {
                v[t->dst].orig=++h;
                coada[h]=t->dst;
            }
        }
    v[i].prez=0;
    v[i].verif=1;
}

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=1;i<=h;i++)trk(coada[i]);
    for(i=2;i<=n;i++)g<<v[i].cst<<' ';
}