#include<stdio.h>
#include<stdlib.h>
#define N 50001
typedef struct nod
{long info;
struct nod *next;}Nod;
typedef struct
{Nod *prim,*ultim;}queue;
typedef struct list
{long x,y;
struct list *urm;};

void add(list *&l,long p,long q)
{list *c=new list;
c->x=p;
c->y=q;
c->urm=l;
l=c;}

long find(list *&l,long p)
{list *c;
for(c=l;c!=NULL;c=c->urm)
if(c->x==p)
       return c->y;
return 10001;}

void push(queue &q,long x)
{Nod *c=new Nod;
c->info=x;
c->next=NULL;
if(q.prim==NULL)
       q.prim=q.ultim=c;
else
       {q.ultim->next=c;
       q.ultim=c;}}
       
long pop(queue &q)
{long x=q.prim->info;
Nod *t=q.prim->next;
free(q.prim);
q.prim=t;
if(q.prim==NULL)
       q.ultim=NULL;
return x;}

int main()
{long n,m,i,j,k;
int c[N],d[N],p,co;
freopen("bellmanford.in","r",stdin);
freopen("bellmanford.out","w",stdout);
queue q;
q.prim=q.ultim=NULL;
list *l[N];
scanf("%ld%ld",&n,&m);
for(i=1;i<=n;i++)
      {c[i]=0;
      d[i]=10001;
      l[i]=NULL;}
for(k=1;k<=m;k++)
      {scanf("%ld%ld%ld",&i,&j,&co);
      add(l[i],j,co);}
d[1]=0;
c[1]=1;
p=0;
for(k=1;k<=n;k++)
      {push(q,k);
      while(q.prim!=NULL)
             {i=pop(q);
             c[i]=1;
             for(j=2;j<=n;j++)
             if(d[j]>d[i]+find(l[i],j))
                      {d[j]=d[i]+find(l[i],j);
                      if(c[j]==0)
                              push(q,j);}}
      for(j=2;j<=n;j++)
      if(d[j]>d[k]+find(l[k],j))
             p=1;}
if(p==0)
      {for(i=2;i<=n;i++)
             printf("%ld ",d[i]);}
else
      printf("Ciclu negativ!");
fclose(stdin);
fclose(stdout);
return 0;}