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

#define INF 0x3f3f3f3f

struct Edge {
  int from, to, cost;
  Edge(int from, int to, int cost): from(from), to(to), cost(cost) {}
};

int main() {
  std::ifstream in("bellmanford.in");
  std::ofstream out("bellmanford.out");
  
  int n, m;
  in >> n >> m;
  
  std::vector<std::vector<Edge>> graph;
  std::vector<int> dist;
  std::vector<int> pred;
  std::vector<int> updated;
  graph.reserve(n);
  dist.reserve(n);
  pred.reserve(n);
  updated.reserve(n);
  for (int i = 0; i < n; i++) {
    graph.push_back(std::vector<Edge>());
    dist.push_back(INF);
    pred.push_back(-1);
    updated.push_back(true);
  }
  for (int i = 0; i < m; i++) {
    int from, to, cost;
    in >> from >> to >> cost;
    graph[from - 1].push_back(Edge(from, to, cost));
  }
  
  dist[0] = 0;
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n; j++) {
      if (updated[j]) {
        bool nowUpdated = false;
        for (Edge& e : graph[j]) {
          if (dist[e.to - 1] > dist[e.from - 1] + e.cost) {
            dist[e.to - 1] = dist[e.from - 1] + e.cost;
            pred[e.to - 1] = e.from;
            nowUpdated = true;
          }
        }
        updated[j] = nowUpdated;
      }
    }
  }
  
  for (int i = 0; i < n; i++) {
    for (Edge& e : graph[i]) {
      if (dist[e.to - 1] > dist[e.from - 1] + e.cost) {
        out << "Ciclu negativ!";
        return 0;
      }
    }
  }
  
  for (int i = 1; i < n; i++) {
    out << dist[i] << " ";
  }
  
  return 0;
}