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

#define MAXN 50'005

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

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

bool inqueue[MAXN];
int cnt[MAXN];
std::deque<int> q;

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[a].push_back({b, cost});
  }

  for (int i = 0; i <= n; i++)
    dist[i] = INT_MAX;

  dist[1] = 0;
  bool cycle = false;
  q.push_back(1);
  inqueue[1] = true;
  while (!q.empty() && !cycle) {
    int curr = q.front();
    inqueue[curr] = false;
    q.pop_front();
    for (auto e : g[curr]) {
      if (dist[e.to] > dist[curr] + e.dist) {
        dist[e.to] = dist[curr] + e.dist;
        if (!inqueue[e.to])
          cycle = (cnt[e.to] > n);
        q.push_back(e.to);
        inqueue[e.to] = true;
        cnt[e.to]++;
      }
    }
  }

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

  return 0;
}