#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <float.h>

#define INF 0x3f3f3f3f

typedef struct
{
  int from, to;
  int weight;
} graph;

graph myGraph[250000];
int dist[50000];

int main(int argc, char *argv[])
{
  freopen ("bellmanford.in", "r", stdin);
  freopen ("bellmanford.out", "w", stdout);
  
  int n, m;
  assert (scanf ("%d%d", &n, &m) == 2);

  int i, j;
  for (i = 0; i < m; ++i){
    assert (scanf ("%d%d%d", &myGraph[i].from, &myGraph[i].to, &myGraph[i].weight) == 3);

    myGraph[i].from--;
    myGraph[i].to--;
  }

  for (i = 0; i < n; ++i)
    if (i == 0)
      dist[i] = 0;
    else
      dist[i] = INF;

  for (i = 0; i < n - 1; ++i)
    for (j = 0; j < m; ++j)
      if (dist [myGraph[j].from] + myGraph[j].weight < dist[myGraph[j].to])
	dist[myGraph[j].to] = dist [myGraph[j].from] + myGraph[j].weight;

  for (i = 0; i < m; ++i)
    if (dist [myGraph[i].from] + myGraph[i].weight < dist[myGraph[i].to])
      {
	printf ("Ciclu negativ!\n");
	exit (0);
      }
  
  for (j = 1; j < n; ++j)
    printf ("%d ", dist[j]);
  printf ("\n");
  
  return 0;
}