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

using namespace std;

struct Node
{
  int cost = (1 << 25);
  vector<pair<int, int>> edges;
};

using Graph = vector<Node>;

bool BellmanFord(Graph &g)
{
  vector<bool> in_queue(g.size(), false);
  vector<int> updates(g.size(), 0);
  queue<int> q;

  q.push(0);
  g[0].cost = 0;

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

    in_queue[node] = false;
    updates[node] += 1;

    if (updates[node] >= (int)g.size()) {
      return true;
    }

    for (const auto &edge : g[node].edges) {
      auto next = edge.first;
      auto cost = g[node].cost + edge.second;

      if (cost < g[next].cost) {
        g[next].cost = cost;
        if (!in_queue[next]) {
          q.push(next);
          in_queue[next] = true;
        }
      }
    }
  }
  return false;
}

int main()
{
  ifstream fin("bellmanford.in");
  ofstream fout("bellmanford.out");

  int nodes, edges;
  fin >> nodes >> edges;

  Graph graph(nodes);
  for (int i = 0; i < edges; ++i) {
    int x, y, cost;
    fin >> x >> y >> cost;
    graph[x - 1].edges.push_back({y - 1, cost});
  }

  auto has_cycle = BellmanFord(graph);
  if (has_cycle) {
    fout << "Ciclu negativ!\n";
    return 0;
  }

  for (int i = 1; i < nodes; ++i) {
    fout << graph[i].cost << " ";
  }
  return 0;
}