#include <cstdio>

using namespace std;

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

int sum;
int c[100][100];
int cmin[100];
int tata[100];
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 <= mch; i++)
  {
    fscanf(intrare,"%d %d %d", &x, &y, &cst);
    c[x][y] = cst;
    sum += abs(cst);
  }
  
  for(i = 1; i <= n; i++)
    for(j = 1; j <= n; j++)
        if (!c[i][j] && i != j)
          c[i][j] = sum;
  
  for(i = 1; i <= n; i++)
  {
    cmin[i] = c[start][i];
    if (i == start)
      tata[i] = 0;
    else
      tata[i] = start;
  }
  
  for(k = 1; k < n; k++)
  {
    for(i = 1; i <= n; i++)
      for(j = 1; j <= n; j++)
        if(c[i][j] != sum)
          if(cmin[i] + c[i][j] < cmin[j])
          {
            cmin[j] = cmin[i] + c[i][j];
            tata[j] = i;
          }
  }
  
  for(i = 1; i <= n; i++)
    for(j = 1; j <= n; j++)
      if(c[i][j] != sum)
        if(cmin[i] + c[i][j] < cmin[j])
        {
          sol = false;
          break;
        }
  
  if (sol == false)
    fprintf(iesire,"Ciclu negati!\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;
}