#include <bits/stdc++.h>
#define MAXN 50005
#define oo ((1LL<<31)-1)
using namespace std;

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

int nodes,
    edges;

vector<pair<int, int>> Graph[MAXN];
int distMin[MAXN];

queue<int> q;
bitset<MAXN> inQueue;
int countInQueue[MAXN];
bool negative_cycle = false;

void read() {
  int x, y, cost;

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

  fin.close();
}

void BellmanFord() {
  for (int i = 2; i <= nodes; i++) distMin[i] = oo;
  distMin[1] = 0;

  q.push(1);
  inQueue[1] = true;

  while (!q.empty() && !negative_cycle) {
    int node = q.front();
    q.pop();
    inQueue[node] = false;

    for (auto it: Graph[node])
      if (distMin[it.first] > distMin[node] + it.second) {
        distMin[it.first] = distMin[node] + it.second;

        if (!inQueue[it.first]) {
          if (countInQueue[it.first] > nodes) negative_cycle = true;
          else {
            q.push(it.first);
            inQueue[it.first]=true;

            countInQueue[it.first]++;
          }
        }
      }
  }
}

void print() {
  if (negative_cycle) fout << "Ciclu negativ!";
  else for (int i = 2; i <= nodes; i++)
      fout << distMin[i] << " ";

  fout.close();
}

int main() {

  read();
  BellmanFord();
  print();

  return 0;
}