#include <bits/stdc++.h>

using namespace std;

const int N = 50005;
const int INF = 0x3f3f3f3f;

vector< pair<int, int> > g[N];
bitset<N> q_in(false);
int dist[N];
int q_count[N];
int n, m;

bool bellman_ford(int source) {
  dist[source] = 0;
  queue<int> q;
  q.push(source);
  q_in[source] = true;
  q_count[source]++;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    q_in[source] = false;
    for (pair<int, int>& e : g[u]) {
      int v = e.second, weight = e.first;
      if (dist[v] > dist[u] + weight) {
        dist[v] = dist[u] + weight;
        if (!q_in[v]) {
          if (q_count[v] > n) {
            return false;
          } else {
            q.push(v);
            q_in[v] = true;
            q_count[v]++;
          }
        }
      }
    }
  }
  return true;
}

int main() {
  freopen("bellmanford.in", "r", stdin);
  freopen("bellmanford.out", "w", stdout);
  for (int i = 0; i < N; i++) {
    dist[i] = INF;
    q_count[i] = 0;
  }
  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; i++) {
    int x, y, w;
    scanf("%d %d %d", &x, &y, &w);
    x--, y--;
    g[x].push_back({w, y});
  }
  bool ret = bellman_ford(0);
  if (!ret) {
    puts("Ciclu negativ!");
    return 0;
  }
  for (int i = 1; i < n; i++) {
    printf("%d ", dist[i]);
  }
  puts("");
  return 0;
}