#include <bits/stdc++.h>
#define INF 1000000001
#define L 50005
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

vector <pair <int, int>> G[L];
queue <int> q;
int dist[L], freq[L], n;

bool bellman_ford(int src){
  int i, node;
  for (i = 1; i <= n; i++)
    dist[i] = INF;
  dist[src] = 0;
  q.push(src);
  while (!q.empty()){
    node = q.front();
    freq[node]++;
    if (freq[node] > n)
      return false;
    for (auto it : G[node])
      if (dist[node] + it.second < dist[it.first]){
        dist[it.first] = dist[node] + it.second;
        q.push(it.first);
      }
    q.pop();
  }
  return true;
}

int main(){
  int m, a, b, c, i, src;
  fin >> n >> m;
  for (i = 0; i < m; i++){
    fin >> a >> b >> c;
    G[a].push_back({b, c});
  }
  src = 1;
  if (bellman_ford(src))
    for (i = 2; i <= n; i++)
      fout << dist[i] << " ";
  else
    fout << "Ciclu negativ!";
  fout << "\n";
  return 0;
}