#include<fstream>
#include<algorithm>
#include<cstring>
#define inf 0x3f3f3f3f
using namespace std;

typedef struct lnod {
      int info,vf;
      lnod *next;  
}*nod;

int i,n,m,st,dr,z,d[50005],nrq[50005],aux,q[50005];
bool viz[50005],u;
nod lda[50005];

void add(int x,int z,nod &y) {
    nod p=new lnod;
    p->info=z;
    p->vf=x;
    p->next=y;
    y=p; 
}

int main()
{
  ifstream cin("bellmanford.in");
  ofstream cout("bellmanford.out");
  
  cin>>n>>m;
  for(i=1;i<=m;++i) cin>>st>>dr>>z,add(dr,z,lda[st]); 
  
  memset(d,inf,sizeof(d));
  viz[1]=1; q[1]=1; st=1; dr=1; d[1]=0;
  
  for(st=1;st<=dr;++st)
  {
    aux=q[st];
    viz[aux]=0;
    
    for(nod p=lda[aux];p;p=p->next)
    if(d[aux]+p->info<d[p->vf])
    {
      d[p->vf]=d[aux]+p->info;
      if(!viz[p->vf]) {
                        q[++dr]=p->vf;
                        viz[p->vf]=1;
                        ++nrq[p->vf];
                        if(nrq[p->vf]==n) u=1,p=0,st=dr+1;
                      }                         
    }                   
  }
  
  if(u) cout<<"Ciclu negativ!"<<'\n';
  else for(i=2;i<=n;++i) if(d[i]==inf) cout<<"0 "; else cout<<d[i]<<' ';
   
 return 0;   
}