#include<fstream>
#define inf 1000
using namespace std;
long dist[500001],n,m,mc[250001][3];

void BF(){
     for(long i=1;i<=n;i++)
      for(long j=1;j<=m;j++)
      if(dist[mc[j][0]]+mc[j][2] < dist[mc[j][1]])
        dist[mc[j][1]]=dist[mc[j][0]]+mc[j][2];}
        

int main(){
    fstream f("bellmanford.in",ios::in);
    fstream g("bellmanford.out",ios::out);
  
f>>n>>m;
for(long i=1;i<=m;i++)
f>>mc[i][0]>>mc[i][1]>>mc[i][2];

dist[1]=0;
for(long i=2;i<=n;i++)
dist[i]=inf;

BF();

int ciclu=0;
for(long i=1;i<=m;i++)
 if(dist[mc[i][0]]+mc[i][2]<dist[mc[i][2]])
  ciclu=1;

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