#include <fstream>
#include <queue>
#include <vector>

std::ifstream in("bellmanford.in");
std::ofstream out("bellmanford.out");

const int N = 5e4 + 1;
const int M = 25e4 + 1;
const long long INF = 25e7 + 1;
int n, m;
std::vector<std::pair<int, int>> g[N];
int cnt[N];
long long minCost[N];
bool inQueue[N];

bool negative_cycle() {
  std::queue<int> q;
  std::fill(minCost + 1, minCost + n + 1, INF);

  minCost[1] = 0;
  q.push(1);
  inQueue[1] = true;
  while (!q.empty()) {
    int currNode = q.front();
    q.pop();
    inQueue[currNode] = false;
    for (auto branch : g[currNode]) {
      int node = branch.first;
      int len = branch.second;
      if (minCost[currNode] + len < minCost[node]) {
        minCost[node] = minCost[currNode] + len;
        if (!inQueue[node]) {
          ++cnt[node];
          if (cnt[node] > n)
            return true;
          q.push(node);
          inQueue[node] = true;
        }
      }
    }
  }
  return false;
}

int main() {
  in >> n >> m;
  for (int i = 0; i < m; ++i) {
    int u, v, cost;
    in >> u >> v >> cost;
    g[u].push_back({v, cost});
  }
  if (negative_cycle()) {
    out << "Ciclu negativ!";
    return 0;
  }
  for (int i = 2; i <= n; ++i) {
    out << minCost[i] << ' ';
  }
}