#include<fstream>
const int inf=1<<30;
using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

int c[50001],poz[50001];
int m,n,i,j,nrviz,aux;

struct muchie
{int node, cost;
 muchie* next;};

int begin, end; 
muchie* a[50001];

void add(int x, int y, int z)
{muchie* q = new muchie;
 q->cost=z;
 q->node=y;
 q->next=a[x];
 a[x]=q;}

int viz[50001],coada[50001],change;
int negativ;
int main()
{f>>n>>m;
int x,y,z;
for(i=1; i<=m; i++)
  {f>>x>>y>>z;
  add(x,y,z);}
for(i=2; i<=n; i++)
  c[i]=inf;
c[1]=0;  
negativ=1;
begin=end=1;
viz[1]=1;
coada[1]=1;

 while(begin<=end && !negativ)
 {
 muchie* q=a[coada[begin]];
 j=coada[begin];
 begin++;
 while(q)
  { if(c[q->node]>c[j]+q->cost)
      {  c[q->node]=c[j]+q->cost;
        if(poz[q->node]==0)
         {end++;  coada[end]=q->node;   poz[q->node]=end;}   
        else
          if(poz[q->node]<begin)
            {if(coada[end-1]==coada[poz[q->node]-1])
                  {negativ=1;  break;}
             begin--;
             aux=coada[begin];
             coada[begin]=q->node;
             q->node=aux;
             poz[coada[begin]]=poz[q->node];
             poz[q->node]=begin;} 
         }      
   q=q->next;} 
   
  }       
 

    
if(!negativ)
 for(i=2; i<=n; i++)
    g<<c[i]<<" ";  
else
 g<<"Ciclu negativ!";         
f.close();
g.close();    
return 0;}