#include <cstdio>
#define INF 1000000000
using namespace std;

FILE * intrare = fopen("bellmanford.in","r");
FILE * iesire = fopen("bellmanford.out","w");

int sum;
int c[10000][10000];
int cmin[10000];
int n, start, mch;
int ind;

bool sol = true;

int abs(int a);

int main()
{
  int x, y, cst, i, j, k;
  fscanf(intrare,"%d%d",&n,&mch);
  
  start = 1;
  
  for(i = 1; i <= n; i++)
    for(j = 1; j <= n; j++)
        if (i != j)
          c[i][j] = INF;

  for(i = 1; i <= mch; i++)
  {
    fscanf(intrare,"%d %d %d", &x, &y, &cst);
    c[x][y] = cst;
  }
        
  for(i = 1; i <= n; i++)
    cmin[i] = INF;
  
  cmin[start] = 0;
  
  for(k = 1; k < n; k++)
  {
    for(i = 1; i <= n; i++)
      for(j = 1; j <= n; j++)
        if(c[i][j] != INF)
          if(cmin[i] + c[i][j] < cmin[j])
            cmin[j] = cmin[i] + c[i][j];
  }
  
  for(i = 1; i <= n; i++)
    for(j = 1; j <= n; j++)
      if(c[i][j] != INF)
        if(cmin[i] + c[i][j] < cmin[j])
        {
          sol = false;
          break;
        }
  
  if (sol == false)
    fprintf(iesire,"Ciclu negativ!\n");
  else
    for(i = 2; i <= n; i++)
      fprintf(iesire,"%d ", cmin[i]);
    fprintf(iesire,"\n");
  
  fclose(iesire);
  return 0;
}

int abs(int a)
{
  if(a < 0)
    return -1 * a;
  return a;
}