#include <bits/stdc++.h>

using namespace std;

const int MAXN = 50005;
const int INF = 1000000000;

vector<pair<int, int> >G[MAXN];

int dist[MAXN];
bool inq[MAXN];
int nq[MAXN];

int main() {
  freopen("bellmanford.in", "r", stdin);
  freopen("bellmanford.out", "w", stdout);

  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; ++i) {
    int u, v, c;
    scanf("%d%d%d", &u, &v, &c);
    G[u].push_back({v, c});
  }

  for (int i = 1; i <= n; ++i)
    dist[i] = INF;

  queue<int>q;
  q.push(1);
  inq[1] = 1;
  nq[1] = 1;
  dist[1] = 0;
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    inq[x] = 0;
    for (auto it:G[x]) {
      if (dist[x] + it.second < dist[it.first]) {
        dist[it.first] = dist[x] + it.second;
        if (!inq[it.first]) {
          q.push(it.first);
          inq[it.first] = 1;
          nq[it.first]++;
          if (nq[it.first] == n) {
            printf("Ciclu negativ!\n");
            return 0;
          }
        }
      }
    }
  }

  for (int i = 2; i <= n; ++i)
    printf("%d ", dist[i]);

  return 0;
}