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

using namespace std;

const int NMAX = 50005;

class Edge {
  public:
    Edge(int uu, int vv, int w): u(uu), v(vv), weight(w) {}
    int u, v, weight;
};

vector<Edge> adj[NMAX];
int dist[NMAX];
int n, m;

int main() {
  ifstream fin;
  fin.open("bellmanford.in");

  fin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v, w;
    fin >> u >> v >> w;
    Edge edge(u, v, w);
    adj[u].push_back(edge);
  }
  fin.close();

  for (int i = 0; i <= n; i++) {
    dist[i] = numeric_limits<int>::max() / 4;
  }

  int src = 1;
  dist[src] = 0;

  queue<int> qu;
  qu.push(src);

  while (!qu.empty()) {
    int u = qu.front();
    qu.pop();
    for (auto edge : adj[u]) {
      int v = edge.v;
      int weight = edge.weight;
      if (dist[u] + weight < dist[v]) {
        dist[v] = dist[u] + weight;
        qu.push(v);
      }
    }
  }

  ofstream fout;
  fout.open("bellmanford.out");

  for (int u = 1; u <= n; u++) {
    for (auto edge : adj[u]) {
      if (dist[u] + edge.weight < dist[edge.v]) {
        fout << "Ciclu negativ!" << endl;
        return 0;
      }
    }
  }

  for (int i = 2; i <= n; i++) {
    if (i != 2) {
      fout << " ";
    }
    fout << dist[i];
  }

  fout.close();

  return 0;
}