#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[500005],q[500005],viz[500005];
bool u=0;
nod lda[500005];

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));
  q[1]=1; st=1; dr=1; d[1]=0;
  
  for(st=1;st<=dr;++st)
  {    
    for(nod p=lda[q[st]];p;p=p->next)
    if(d[q[st]]+p->info<d[p->vf])
    {
      d[p->vf]=d[q[st]]+p->info;
      q[++dr]=p->vf; ++viz[p->vf];
      if(viz[p->vf]==n) {u=1;break;}
    }                   
    if(u) break;
  }
  
  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;   
}