#include <cstdio>
#include <cassert>
#include <cstdlib>
#define Nmax 50005
#define INF 9000000
#define InFile "bellmanford.in"
#define OutFile "bellmanford.out"

using namespace std;

int n, m, sl;
int d[Nmax];
int Q[Nmax*30];
int *A[Nmax], *C[Nmax];

void read();
void Bellman_Ford();
void write();

int main()
{
  assert (freopen (InFile, "r", stdin));
  assert (freopen (OutFile, "w", stdout));
  read();
  Bellman_Ford();
  if (!sl)
    write();
  return 0;
}

void read()
{
  int i, x, y, cst;
  scanf ("%d %d\n", &n, &m);
  for (i=1; i<=n; i++) 
  {
    A[i]=(int*) realloc (A[i], sizeof (int)), A[i][0]=0;
    C[i]=(int*) realloc (C[i], sizeof (int)), C[i][0]=0;
  }
  for (i=0; i<m; i++)
  {
    scanf ("%d %d %d\n", &x, &y, &cst);
    C[x][0]++;
    C[x]=(int *) realloc (C[x], (C[x][0]+1)*sizeof (int));
    C[x][C[x][0]]=cst;
    A[x][0]++;
    A[x]=(int *)realloc (A[x], (A[x][0]+1)*sizeof (int));
    A[x][A[x][0]]=y;
  }
}

void Bellman_Ford()
{
  int i, x;
  int sf=-1, inc=0;
  //initial var
  Q[++sf]=1;
  for (i=1; i<=n; i++) d[i]=INF;
  d[1]=0;
  //alg
  while (inc<=sf)
  {
    x=Q[inc++];
    for (i=1; i<=A[x][0]; i++)
      if (d[A[x][i]]>d[x]+C[x][i])
      {
        d[A[x][i]]=d[x]+C[x][i];
        Q[++sf]=A[x][i];
        if (sf==Nmax*30-2)
        {
          printf ("Circuit negativ");
          sl=1;
          return;
        }
      }
  }
}

void write()
{
  int i;
  for (i=2; i<=n; i++)
    printf ("%d ", d[i]);
  printf ("\n");
}