#include<fstream>
using namespace std;
int n,m,i,viz[50002],cost1[50002],ciclunegativ,x,y,val;
struct nodc
{
    int x;
    nodc *leg;
};
// nodc *first,*last;
struct nod
{
    int x,cost,contor;
    nod *leg;
};
nod *first,*last,*p,*q,*v[50002];
int main()
{
     ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");
    fin>>n>>m;
    for(i=1;i<=n;i++)
    {
        v[i]=0;
        viz[i]=0;
        cost1[i]=2000000;
    }
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>val;
        p=new nod;
        p->x=y;
        p->cost=val;
        p->contor=0;
        p->leg=v[x];
        v[x]=p;
    }
    first=new nod;
    first->x=1;
    first->leg=0;
    last=first;
    viz[1]=1;
    ciclunegativ=0;
    cost1[1]=0;
    while(first!=0 && ciclunegativ==0)
    {
        x=first->x;
        for(p=v[x];p!=0;p=p->leg)
        {
            p->contor++;
            if(p->contor==n)
            {
                ciclunegativ=1;
                break;
            }
            if(cost1[x]+p->cost<cost1[p->x])
            {
                cost1[p->x]=cost1[x]+p->cost;
                if(viz[p->x]==0)
                {
                    q=new nod;
                    q->x=p->x;
                    q->cost=cost1[p->x];
                    q->leg=0;
                    last->leg=q;
                    last=q;
                }
            }
        }
        p=first;
        first=first->leg;
        delete p;
    }
    if(ciclunegativ==1)
    {
        fout<<"Ciclu negativ!";
    }
    else
    {
        for(i=2;i<=n;i++)
        {
            fout<<cost1[i]<<" ";
        }
    }
    fin.close();
    fout.close();
    return 0;
}