#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>

const int INF = 2e9;
const int MAXN = 5e4;

struct Edge {
  int u, c;
};

std::vector <Edge> g[MAXN + 1];
int dist[MAXN + 1], t[MAXN + 1];
bool vis[MAXN + 1];
std::queue <int> q;

int main() {
  int n, m, u, v, c;
  bool flag;
  FILE *f = fopen("bellmanford.in", "r");
  fscanf(f, "%d%d", &n, &m);
  for (int i = 0; i < m; ++i) {
    fscanf(f, "%d%d%d", &u, &v, &c);
    g[u].push_back({v, c});
  }
  fclose(f);
  for (int i = 2; i <= n; ++i) {
    dist[i] = INF;
  }
  flag = 0;
  q.push(1);
  while (!q.empty() && !flag) {
    u = q.front();
    q.pop();
    vis[u] = 0;
    for (auto v: g[u]) {
      if (dist[v.u] > dist[u] + v.c) {
        dist[v.u] = dist[u] + v.c;
        ++t[v.u];
        if (t[v.u] >= n) {
          flag = 1;
          break;
        }
        if (!vis[v.u]) {
          vis[v.u] = 1;
          q.push(v.u);
        }
      }
    }
  }
  f = fopen("bellmanford.out", "w");
  if (flag) {
    fprintf(f, "Ciclu negativ!\n");
  } else {
    for (int i = 2; i <= n; ++i) {
      fprintf(f, "%d ", dist[i]);
    }
    fprintf(f, "\n");
  }
  fclose(f);
  return 0;
}