#include <iostream>
#include <stdio.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()
{ FILE *f,*g;
bool ciclu;
int viz[nd],ap[nd],i,n,m,j,d[nd],x,x1,x2,c;
f=fopen("bellmanford.in","r");
g=fopen("bellmanford.out","w");
fscanf(f,"%d%d",&n,&m);
for(i=1;i<=m;i++)
    {
        fscanf(f,"%d%d%d",&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)fprintf(g,"Ciclu negativ!\n");
    else {
            for(i=2;i<=n;i++)
               fprintf(g,"%d ",d[i]);
        }
fclose(f);
fclose(g);
return 0;
}