#include <fstream>
#include <string>
#include <vector>
#include <climits>
#include <queue>
#include <unordered_set>
#include <unordered_map>

const std::string kInputFileName = "bellmanford.in";
const std::string kOutputFileName = "bellmanford.out";

class ShortestPathFinder {
public:
  explicit ShortestPathFinder(std::vector<std::vector<std::pair<int, int>>> graph) :
    graph_(std::move(graph)) {}

  std::vector<int> FindShortestPaths(int source) {
    std::vector<int> cost_to_node(graph_.size(), INT_MAX);
    cost_to_node[source] = 0;

    std::unordered_set<int> nodes_in_queue = {source};
    std::unordered_map<int, int> num_times_in_queue = {{source, 1}};

    std::queue<int> q;
    q.push(source);

    while (!q.empty()) {
      int node = q.front();
      q.pop();

      for (const auto& edge : graph_[node]) {
        const int& adj_node = edge.first;
        const int& cost = edge.second;

        int new_cost = cost_to_node[node] + cost;
        if (new_cost < cost_to_node[adj_node]) {
          cost_to_node[adj_node] = new_cost;
          if (nodes_in_queue.count(adj_node)) {
            continue;
          }
          q.push(adj_node);
          nodes_in_queue.insert(adj_node);
          num_times_in_queue[adj_node]++;
          if (num_times_in_queue[adj_node] >= graph_.size()) {
            return {};
          }
        }
      }

      nodes_in_queue.erase(node);
    }

    return std::move(cost_to_node);
  }

private:
  const std::vector<std::vector<std::pair<int, int>>> graph_;
};

int main() {
  std::ifstream fin(kInputFileName);
  std::ofstream fout(kOutputFileName);

  int num_nodes;
  fin >> num_nodes;

  int num_edges;
  fin >> num_edges;

  std::vector<std::vector<std::pair<int, int>>> graph(
      num_nodes, std::vector<std::pair<int, int>>());
  for (int i = 0; i < num_edges; i++) {
    int start, end, cost;
    fin >> start >> end >> cost;
    graph[start - 1].push_back({end - 1, cost});
  }

  const std::vector<int> result =
    ShortestPathFinder(std::move(graph)).FindShortestPaths(0);

  if (result.empty()) {
    fout << "Ciclu negativ!";
    return 0;
  }

  for (int i = 1; i < result.size(); i++) {
    fout << (result[i] == INT_MAX ? 0 : result[i]) << ' ';
  }
  return 0;
}