#include <fstream>
#include <vector>
#include <deque>

using namespace std;

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

struct Edge{
  int to;
  int weight;
};

int const INF = 1e9 + 7;

int const NMAX = 5e4;
vector<Edge> g[1 + NMAX];
bool visited[1 + NMAX];
int dist[1 + NMAX];

int n, m;

deque <int> q;

bool computeBellmanFord(int nod){

  int cnt = 0, from, to, weight;
  for(int i = 1;i <= n;i++){
    dist[i] = INF;
  }
  dist[nod] = 0;
  q.push_back(nod);
  for(int i = 1;i < m;i++){
    int wave = q.size();
    for(int j = 0;j < wave;j++){
      from = q.front();
      q.pop_front();
      for(int i = 0;i < g[from].size();i++){
        to = g[from][i].to;
        weight = g[from][i].weight;
        if(dist[from] + weight < dist[to]){
          dist[to] = dist[from] + weight;
          q.push_back(to);
        }
      }
    }
    if(q.empty()){
      return true;
    }
  }

  return false;
}

int main() {

  int from, to, weight;
  in >> n >> m;
  for(int i = 1;i <= m;i++){
    in >> from >> to >> weight;
    g[from].push_back({to, weight});
  }
  if(computeBellmanFord(1)){
    for(int i = 2;i <= n;i++){
      out << dist[i] << ' ';
    }
  }else{
    out << "Ciclu negativ!";
  }

  return 0;
}