#include <cstdio>
#include<iostream.h>
#include<fstream.h>
#define nd 50001
#define max 1999999999
using namespace std;
struct nod{int val; int cost; nod *urm; }*p[nd];
nod *aux;
struct coada{int nr; coada *next;}*st,*dr;
coada *adr;
int main()
{ 
bool ciclu;
int viz[nd],ap[nd],i,n,m,j,d[nd],x,x1,x2,c;
fstream f("bellmanford.in",ios::in);
fstream g("bellmanford.out",ios::out);
f>>n>>m;
for(i=1;i<=m;i++)
    {
        f>>x>>x1>>x2;
        aux=new nod;
        aux->val=x1;
        aux->cost=x2;
        aux->urm=p[x];
        p[x]=aux;
    }
for(i=1;i<=n;i++)
    {
        viz[i]=0;
        ap[i]=0;
        d[i]=max;
    }
st=new coada;
st->next=NULL;
st->nr=1;
dr=st;
d[1]=0;
viz[1]=1;
ap[1]=1;
ciclu=false;
while(st!=NULL&&ciclu==false)
    {
        i=st->nr;
        viz[i]=0;
        aux=p[i];
        while(aux!=NULL&&ciclu==false)
            {
                j=aux->val;
                c=aux->cost;
                if(d[j]>d[i]+c)
                {
                    d[j]=d[i]+c;
                    if(viz[j]==0)
                        {
                            viz[j]=1;
                            if(ap[j]>n)ciclu=true;
                            else    {
                                        ap[j]++;
                                        adr=new coada;
                                        adr->nr=j;
                                        adr->next=NULL;
                                        dr->next=adr;
                                        dr=adr;
                                    }
                        }
                }
            aux=aux->urm;
            }
        adr=st;
        st=st->next;
        delete adr;
    }
if(ciclu==true) g<<"Ciclu negativ!";
    else {
            for(i=2;i<=n;i++)
               g<<d[i]<<" ";
        }
f.close();
g.close();
return 0;
}