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

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

int c[250001];
int m,n,i,j,nrviz;

struct muchie
{int source, cost;
 muchie* next;};
 
muchie* a[50001];

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

int viz[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;
for(i=1; i<=n-1; i++)
{for(j=1; j<=n; j++)
 if(viz[j]==0)
 {muchie* q=a[j];
 change=0; 
  while(q)
  {if(c[j]>c[q->source]+q->cost)
    {c[j]=c[q->source]+q->cost;
    change=1;}
    q=q->next;
   }
  if(change==0)
    {viz[j]=1; nrviz++;}
 }
 if(nrviz==n)
   {negativ=0; break;}
}  

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