#include <fstream>
#define NMAX 50000
#define infinit 2000000
using namespace std;
int d[NMAX+10],frecv[NMAX+10],coada[NMAX*5+10];
int n,m,i,j,p,u,ok;
struct nod{
int vf,lung;
nod *urm;
};
nod *v[NMAX+10];

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++){
        int a,b,c;
        f>>a>>b>>c;
        nod *q=new nod;
        q->vf=b;
        q->lung=c;
        q->urm=v[a];
        v[a]=q;
    }
    d[1]=0;
    for(i=2;i<=n;i++)
        d[i]=infinit;
    p=u=1;
    coada[1]=1;
    ok=1;
    while(p<=u&&ok==1){
        for(nod *q=v[coada[p]];q;q=q->urm){
            if(d[q->vf]>d[coada[p]]+q->lung){
                frecv[q->vf]++;
                if(frecv[q->vf]>n)  ok=0;
                d[q->vf]=d[coada[p]]+q->lung;
                coada[++u]=q->vf;
            }
        }
        p++;
    }
    if(ok==0)   g<<"Ciclu negativ!";
    else{
        for(i=2;i<=n;i++)
            if(d[i]==infinit)   g<<"0 ";
        else                    g<<d[i]<<" ";
    }
    return 0;
}