#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9, MAXN = 5e4;


struct edge {
  int fiu, cost, used;
};

vector <edge> gr[MAXN + 1];
int dist[MAXN + 1];

priority_queue <pair <int, int>> heap;

int main() {
  int n, m, i, x, y, c, nod;
  freopen ("bellmanford.in", "r", stdin);
  freopen ("bellmanford.out", "w", stdout);

  scanf ("%d%d", &n, &m);
  for (i = 1; i <= m; i++) {
    scanf ("%d%d%d", &x, &y, &c);
    gr[x].push_back ({y, c, 0});
  }

  for (i = 1; i <= n; i++)
    dist[i] = INF;
  dist[1] = 0;
  heap.push ({0, 1});
  while (heap.empty () == false) {
    nod = heap.top ().second;
    heap.pop ();
    for (edge &x : gr[nod]) {
      if (dist[nod] + x.cost < dist[x.fiu]) {
        x.used++;
        if (x.used == n) {
          printf ("Ciclu negativ!\n");
          return 0;
        }
        dist[x.fiu] = dist[nod] + x.cost;
        heap.push ({-dist[x.fiu], x.fiu});
      }
    }
  }

  for (i = 2; i <= n; i++)
    printf ("%d ", dist[i]);
  printf ("\n");
  return 0;
}