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

using namespace std;

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

struct Edge {
  int to;
  int cost;
};

int const INF = 100000007;

int const NMAX = 6250000;
int dist[1 + NMAX];
int isQueue[1 + NMAX];
vector <Edge> g[1 + NMAX];

void computeBellman(int start, int n) {
  for(int i = 1;i <= NMAX;i++) {
    dist[i] = INF;
    isQueue[i] = false;
  }
  queue <int> q;
  dist[start] = 0;
  isQueue[start] = true;
  q.push(start);
  int ind = 1;
  while(ind < n && !q.empty()) {
    int qSize = q.size();
    for(int t = 0;t < qSize;t++) {
      int from = q.front();
      q.pop();
      isQueue[from] = false;
      for(int i = 0;i < g[from].size();i++) {
        int to = g[from][i].to;
        if(dist[from] + g[from][i].cost < dist[to]) {
          dist[to] = dist[from] + g[from][i].cost;
          if(!isQueue[to]) {
            isQueue[to] = true;
            q.push(to);
          }
        }
      }
    }
    ind++;
  }
  if(!q.empty()) {
    fout << "Ciclu negativ!";
  }else {
    for(int i = 2;i <= n;i++) {
      fout << dist[i] << ' ';
    }
  }
}

int main() {

  int n, m;
  fin >> n >> m;
  for(int i = 1;i <= m;i++) {
    int a, b, cost;
    fin >> a >> b >> cost;
    g[a].push_back({b, cost});
  }
  computeBellman(1, n);
  return 0;
}