#include <fstream>
#include <vector>
#include <queue>
#define NMAX 50000
#define INF 29999999

using namespace std;
// uitasem ca era orientat :///
struct graf{
  int node, cost;
};
int current_node, flag;


void predef (int v[], int f[], int n){
  for (int i = 1; i <= n; i++)
    v[i] = INF, f[i] = 0;
}


vector <graf> v[NMAX + 1];
queue <int> q;
int dist[NMAX + 1], viz[NMAX + 1];

void bellmanford (int nod){
  q.push(nod);
  dist[nod] = 0;
  viz[nod] = 1;

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

    for ( auto neighbour : v[current_node] ){
      if (dist[neighbour.node] > dist[current_node] + neighbour.cost){
        dist[neighbour.node] = dist[current_node] + neighbour.cost;
        if (!viz[neighbour.node]){
          q.push(neighbour.node);
          viz[neighbour.node] = 1;
        }
      }
      viz[current_node] = 0;

    }
  }
  if (!q.empty())
    flag = 1;
}
int main(){

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

  int n, m;
  int a, b, coste;

  fin >> n >> m;
  for (int i = 1; i <= m; i++){

    fin >> a >> b >> coste;
    v[a].push_back({b, coste});
  }

  predef (dist, viz, n);
  bellmanford(1);

  if (flag == 1)
    fout << "Ciclu negativ!\n";
  else
    for (int i = 2; i <= n; i++)
      fout << dist[i] << " ";
  return 0;
}