#include <iostream>
#include<fstream>
using namespace std;
int n,m,i,D[50003],a,b,c,x,M[50003],ok=1;
struct vecin
{
    int v,c;
    vecin *urm;
};
struct nod
{
    int v;
    nod *urm;
};
vecin *LA[50003],*p;
nod *first,*last, *r;
int main()
{
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        p=new vecin;
        p->v=b;
        p->c=c;
        p->urm=LA[a];
        LA[a]=p;
    }
    for(i=1;i<=n;i++)
        D[i]=2000000000;
    D[1]=0;
    first=new nod;
    first->v=1;
    first->urm=0;
    last=first;
    while(first&&ok)
    {
        x=first->v;
        for(p=LA[x];p;p=p->urm)
        {
            if(D[x]+p->c<D[p->v])
            {
                D[p->v]=D[x]+p->c;
                r=new nod;
                r->v=p->v;
                r->urm=0;
                last->urm=r;
                last=r;
                M[a]++;
                if(M[a]==n+1)
                {
                    fout<<"Ciclu negativ!";
                    ok=0;
                }
            }
        }
        r=first;
        first=first->urm;
        delete r;
    }
    if(ok)
    {
    for(i=2;i<=n;i++)
    {
        if(D[i]==2000000000)
            D[i]=0;
        fout<<D[i]<<' ';
    }
    }
fout.close();
return 0;
}