#include<fstream>
#define inf 260000;
using namespace std;
int v[250000][3],d[50000],n,m,i,j,ok=1;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
void cit()
{f>>n>>m;      
for(i=1; i<=m; i++)
   {f>>v[i][0]>>v[i][1]>>v[i][2];}
f.close();}
int nega()
{int ok1=0;
for(i=1;i<=m&&ok==0;i++)
 {if(d[v[i][0]]+v[i][2]<d[v[i][1]])
ok1=1;}
 if(ok==0)        
return 0;
else
return 1;}       
void befo()
{for(i=1;i<=n-1&&ok==1;i++)   
 {ok=0;
   for(j=1;j<=m;j++) 
    if(d[v[j][0]]+v[j][2]<d[v[j][1]])
     {d[v[j][1]]=d[v[j][0]]+v[j][2];
      ok=1;}}}
void inti()
{d[1]=0;
for(i=2;i<=n;i++) 
{d[i]=inf;}}
void puts()
{if(nega()==0)
{for(i=2; i<=n;i++)
g<<d[i]<<" ";}
else 
g<<"Ciclu negativ!";
g.close();} 
 void main1()
{cit(); 
inti();   
befo();
puts();}            
     int main()
{main1();     }