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

#define Inf 99999999

void read_data(const std::string &filename, std::vector<std::vector<int> > &graph, std::vector<std::vector<int> > &costs)
{
  std::ifstream in(filename.c_str());
  int N, M;
  in >> N >> M;

  graph = costs = std::vector<std::vector<int> >(N);

  for (int i = 0; i < M; i++)
  {
    int x, y, z;
    in >> x >> y >> z;
    graph[x - 1].push_back(y - 1), costs[x - 1].push_back(z);
  }
}

void write_data(const std::string &filename, const std::vector<int> &dists)
{
  std::ofstream out(filename.c_str());
  if (dists.size() == 0)
  {
    out << "Ciclu negativ!\n";
    return;
  }
  for (int i = 1; i < static_cast<int>(dists.size()); i++)
    out << dists[i] << ' ';
  out << '\n';
}

void bellmanford(const std::vector<std::vector<int> > &graph, const std::vector<std::vector<int> > &costs, int source, std::vector<int> &dists)
{
  std::queue<int> q;
  std::vector<int> updated(graph.size(), 0);
  std::vector<bool> flags(graph.size(), true);
  
  for (int i = 0; i < static_cast<int>(graph.size()); i++)
    q.push(i);

  dists = std::vector<int>(graph.size(), Inf);    
  dists[source] = 0;
  
  while (!q.empty())
  {
    int t = q.front();
    q.pop();
    flags[t] = false;
    
    for (int i = 0; i < static_cast<int>(graph[t].size()); i++)
      if (dists[t] + costs[t][i] < dists[graph[t][i]])
      {
        updated[graph[t][i]]++;
        if (updated[graph[t][i]] == static_cast<int>(graph.size()))
        {
          dists.clear();
          return;
        }
        dists[graph[t][i]] = dists[t] + costs[t][i];
        if (!flags[graph[t][i]])
        {
          flags[graph[t][i]] = true;
          q.push(graph[t][i]);
        }
      }
  }
}

int main()
{
  std::vector<std::vector<int> > graph, costs;
  read_data("bellmanford.in", graph, costs);
  std::vector<int> dists;
  bellmanford(graph, costs, 0, dists);
  write_data("bellmanford.out", dists);
}