#include <cstdio>
#include <vector>
#include <deque>

using namespace std;

const int MAX_N = 50000;
const int MAX_M = 250000;
const int INF = 1000000000;

struct Edge {
  int to, cost, freq;
};

vector<Edge> edges;
vector<vector<int> > graph;
vector<int> cost;

int main() {
  int n, m;
  int a, b, c;
  int src;
  bool infiniteCycle;

  FILE *fin = fopen("bellmanford.in", "r");
  fscanf(fin, "%d%d", &n, &m);

  graph.resize(n + 1, vector<int>());
  cost.resize(n + 1, INF);

  for(int i = 0; i < m; ++i) {
    fscanf(fin, "%d%d%d", &a, &b, &c);
    graph[a].push_back(edges.size());
    edges.push_back({b, c, 0});
  }
  fclose(fin);

  src = 1;

  cost[1] = 0;
  deque<int> coada;
  coada.push_back(1);

  infiniteCycle = false;
  while(!coada.empty() && !infiniteCycle) {
    int nod = coada.front();
    coada.pop_front();

    for(auto it: graph[nod]) {
      if(cost[nod] + edges[it].cost < cost[edges[it].to]) {
        cost[edges[it].to] = cost[nod] + edges[it].cost;
        coada.push_back(edges[it].to);
        edges[it].freq++;

        if(edges[it].freq > n)
          infiniteCycle = true;
      }
    }
  }

  FILE *fout = fopen("bellmanford.out", "w");
  if(infiniteCycle)
    fprintf(fout, "Ciclu negativ!");
  else {
    for(int i = 2; i <= n; ++i)
      fprintf(fout, "%d ", cost[i]);
  }
  fclose(fout);

  return 0;
}