#include<stdio.h>
#include<stdlib.h>
#include<queue>
#define FIN "bellmanford.in"
#define FOUT "bellmanford.out"
#define NMAX 50004
#define MMAX 250004
#define inf 0x3f3f3f3f
using namespace std;

struct nod
{  int info,cost;
   nod* next;
       } *g[NMAX];
typedef nod* Lista;       
int n,m,i,j,x,y,c,viz[NMAX],nr[NMAX],dist[NMAX];

void add(Lista  &p,int x,int c)
 {   nod* q=new nod;
     q->info=x;
     q->cost=c;
     q->next=p;
     p=q; 
}     
int empty(Lista Q)
 {return Q==NULL;}
int main()
{
    freopen(FIN,"r",stdin);
    freopen(FOUT,"w",stdout);
    scanf("%d %d",&n,&m); 
    for(int i=1;i<=m;i++)
      {
      scanf("%d %d %d",&x,&y,&c);
      add(g[x],y,c);
            } 
          
  for(int i=2;i<=n;i++) dist[i]=inf;
  dist[1]=0;
  queue<int> Q;
  Q.push(1);
  viz[1]=1;
  nr[1]++;   
  int ciclu_negativ=0;   
  while(!Q.empty() && !ciclu_negativ)
   {
    int x=Q.front();
    Q.pop();
    viz[x]=0;
    for(nod* i=g[x];i;i=i->next)
    {
     if(dist[x]<inf)
      if(dist[i->info]>dist[x]+i->cost)
       {
         dist[i->info]=dist[x]+i->cost;
         if(!viz[i->info])
          if(nr[i->info]>n) ciclu_negativ=1;
          else{
               Q.push(i->info);
               viz[i->info]=1; 
               nr[i->info]++; 
             }
           }
       }
     }  
   if(ciclu_negativ) printf("Ciclu negativ!\n");
   else for(int i=2;i<=n;i++) printf("%d ",dist[i]);          
    return 0;
    }