#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

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

int const nmax = 50000;

struct Edge {
    int to;
    int cost;
};

int n, m;
vector<Edge> g[1 + nmax];
int vis[1 + nmax];
int sol[1 + nmax];

bool bfs(){
  queue<int> q;
  q.push(1); //determini distanta minima de la nodul 1 la fiecare nod din graf
  vis[1] = 1;
  while(0 < q.size()) {
    int node = q.front();
    q.pop();
    for(int i = 0; i < g[node].size(); i++) {
      Edge &e = g[node][i];
      if(vis[e.to] == 0 || sol[node] + e.cost < sol[e.to]) {
        if(vis[e.to] == n){
          return 0;
        }
        sol[e.to] = sol[node] + e.cost;
        vis[e.to]++;
        q.push(e.to);
      }
    }
  }
  return 1;
}

int main() {
  in >> n >> m;
  for (int i = 1; i <= m; i++) {
    int a, b, c;
    in >> a >> b >> c;
    g[a].push_back({b, c});
  }
  queue<int> q;
  if(bfs()) {
    for(int i = 2 ; i <= n ;i++){
      out<<sol[i]<<" ";
    }
  } else
    out << "Ciclu negativ!";
  return 0;
}