#include <bits/stdc++.h>
using namespace std;

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

#define PII pair<int, int>

int main()
{
  int n, m;
  fin >> n >> m;

  vector<vector<PII>> graph(n + 1);
  for (int i = 1; i <= m; i++)
  {
    int x, y, c;
    fin >> x >> y >> c;
    graph[x].push_back({y, c});
  }

  vector<int> cost(n + 1, INT_MAX), vis(n + 1, 0);

  queue<int> nodeQ;
  nodeQ.push(1);
  cost[1] = 0;

  while (!nodeQ.empty())
  {
    int curr = nodeQ.front();
    nodeQ.pop();

    vis[curr]++;
    if (vis[curr] >= n)
    {
      fout << "Ciclu negativ!";
      return 0;
    }

    for (PII &next : graph[curr])
      if (cost[next.first] > cost[curr] + next.second)
      {
        cost[next.first] = cost[curr] + next.second;
        nodeQ.push(next.first);
      }
  }

  for (int i = 2; i <= n; i++)
    fout << cost[i] << " ";

  return 0;
}