#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;
  graph.reserve(n);
  dist.reserve(n);
  pred.reserve(n);
  for (int i = 0; i < n; i++) {
    graph.push_back(std::vector<Edge>());
    dist.push_back(INF);
    pred.push_back(-1);
  }
  std::queue<Edge> current;
  std::queue<Edge> additional;
  for (int i = 0; i < m; i++) {
    int from, to, cost;
    in >> from >> to >> cost;
    graph[from - 1].push_back(Edge(from, to, cost));
    current.push(Edge(from, to, cost));
  }
  
  dist[0] = 0;
  for(int i = 0; i < n - 1 && !current.empty(); i++) {
    while (!current.empty()) {
      Edge& curr = current.front();
      current.pop();
      if (dist[curr.to - 1] > dist[curr.from - 1] + curr.cost) {
        dist[curr.to - 1] = dist[curr.from - 1] + curr.cost;
        pred[curr.to - 1] = curr.from;
        for (Edge& e : graph[curr.to - 1]) {
          additional.push(e);
        }
      }
    }
    current = additional;
  }
  
  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;
}