#include <iostream>
#include <cstdio>

using namespace std;

struct muchie{
  int a, b, cost;
};

muchie v[250001];
int dist[50001];

int main() {
  FILE *fin, *fout;
  int n, m, i, j, x, y, c, st;
  fin=fopen("bellmanford.in","r");
  fout=fopen("bellmanford.out","w");
  fscanf(fin, "%d%d",&n,&m);
  for(i=1;i<=m;i++) {
    fscanf(fin, "%d%d%d",&x,&y,&c);
    v[i].a=x;
    v[i].b=y;
    v[i].cost=c;
  }
  for(i=1;i<=n;i++)
    dist[i]=1000000000;
  dist[1]=0;
  for(i=1;i<n;i++)
    for(j=1;j<=m;j++)
      if(dist[v[j].a]+v[j].cost<dist[v[j].b])
        dist[v[j].b]=dist[v[j].a]+v[j].cost;
  st=1;
  for(i=1;i<n;i++)
    for(j=1;j<=m;j++)
      if(dist[v[j].a]+v[j].cost<dist[v[j].b]) {
        st=0;
        break;
      }
  if(st==0)
    fprintf(fout, "Ciclu negativ!");
  else
    for(i=2;i<=n;i++)
      fprintf(fout, "%d ",dist[i]);
  fclose( fin );
  fclose( fout );
  return 0;
}