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

#define N_MAX 50000
#define INF ((1) << (30))

typedef struct Node {
  int data;
  int weight;
  struct Node * next;
} Node;

Node *G[N_MAX];
int shortest[N_MAX];

void add(int from, int to, int weight) {
  Node * p = malloc(sizeof(Node));
  p->data = to;
  p->weight = weight;
  p->next = G[from];
  G[from] = p;
}

void read(int m, FILE * in) {
  int i, from, to, weight;

  for (i = 1; i <= m; i++) {
    fscanf(in, "%d %d %d", &from, &to, &weight);
    add(from - 1, to - 1, weight);
  }
}

void bellmanFord(int source, int n) {
  int i, j;
  Node *p;

  for (i = 0; i < n; i++) {
    shortest[i] = INF;
  }
  shortest[source] = 0;

  for (i = 1; i <= n - 1; i++)
    for (j = 0; j < n; j++)
      for (p = G[j]; p; p = p->next)
        if (p->weight + shortest[j] < shortest[p->data])
          shortest[p->data] = shortest[j] + p->weight;

}

int findNegativeCicle(int n) {
  int i;
  Node * p;

  for (i = 0; i < n; i++) {
    for (p = G[i]; p; p = p->next) {
      if (shortest[i] + p->weight < shortest[p->data])
        return 1;
    }
  }

  return 0;
}

int main() {
  FILE * in, * out;
  int n, m, i, hasNegativeCicle;

  in = fopen("bellmanford.in", "r");
  fscanf(in, "%d %d", &n, &m);
  read(m, in);

  bellmanFord(0, n);

  out = fopen("bellmanford.out", "w");
  hasNegativeCicle = findNegativeCicle(n);
  if (!hasNegativeCicle) {
    for (i = 1; i < n; i++) {
      fprintf(out, "%d ", shortest[i]);
    }
  }
  else {
    fprintf(out, "Ciclu negativ!");
  }

  return 0;
}