// SOURCE: infoarena
#include <climits>
#include <stdio.h>
#include <vector>

#define MAXN 50'005

int n, m;
struct Edge {
  int from;
  int to;
  int dist;
};

std::vector<Edge> g;
int dist[MAXN];

int main() {
  freopen("bellmanford.in", "r", stdin);
  freopen("bellmanford.out", "w", stdout);
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    int a, b, cost;
    scanf("%d%d%d", &a, &b, &cost);
    g.push_back({a, b, cost});
  }

  for (int i = 0; i <= n; i++)
    dist[i] = INT_MAX;
  dist[1] = 0;
  bool cycle = false;
  for (int i = 0; i < n; i++) {
    bool any = false;
    for (auto edge : g) {
      if (dist[edge.from] != INT_MAX &&
          dist[edge.from] + edge.dist < dist[edge.to]) {

        if (i == n - 1) {
          cycle = true;
          break;
        }

        dist[edge.to] = dist[edge.from] + edge.dist;
      }

      if (!any)
        break;
    }
  }

  if (cycle) {
    printf("Ciclu negativ!\n");
    return 0;
  }
  for (int i = 2; i <= n; i++)
    printf("%d ", dist[i]);
  printf("\n");

  return 0;
}