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

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

int a[50001][3];
int c[250001];
int m,n,i,j;

int main()
{f>>n>>m;
for(i=1; i<=m; i++)
  f>>a[i][0]>>a[i][1]>>a[i][2];
for(i=2; i<=n; i++)
  c[i]=inf;
c[1]=0;  
for(i=1; i<=n-1; i++)
 for(j=1; j<=m; j++)  
  if(c[a[j][1]]>c[a[j][0]]+a[j][2])
    c[a[j][1]]=c[a[j][0]]+a[j][2];
int negativ=0;
for(i=1; i<=m; i++)
  if(c[a[i][1]]>c[a[i][0]]+a[i][2])
    {negativ=1;
     break;}
g<<"Ciclu negativ!";     
if(!negativ)
 for(i=2; i<=n; i++)
    g<<c[i]<<" ";      
f.close();
g.close();    
return 0;}