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

#define INF 250000000

using namespace std;

class graph {
  int vertices;
  int edges;
  vector<vector<pair<int, int>>> adj;
  vector<int> distance;

public:
  graph(int n, int m) : vertices(n), edges(m), adj(n), distance(n, INF) {};
  void read_neighbours(istream& in) {
    int v1, v2, w;
    for (int i = 0; i < edges; i++) {
      in >> v1 >> v2 >> w;
      adj[v1 - 1].push_back(make_pair(v2 - 1, w));
    }
  }
  int bellman_ford(int src) {
    distance[src] = 0;
    for (int i = 0; i < vertices; i++) {
      for (int v1 = 0; v1 < vertices; v1++) {
        for (auto v2 : adj[v1]) {
          if (distance[v1] + v2.second < distance[v2.first]) {
            distance[v2.first] = distance[v1] + v2.second;
          }
        }
      }
    }
    for (int i = 0; i < vertices; i++) {
      for (int v1 = 0; v1 < vertices; v1++) {
        for (auto v2 : adj[v1]) {
          if (distance[v1] + v2.second < distance[v2.first]) {
            return -1;
          }
        }
      }
    }
    return 1;
  }
  void print_distances(ostream& out, int src) {
    if (bellman_ford(src - 1) == -1) {
      out << "Ciclu negativ!" << endl;
      return;
    }
    for (int i = src; i < vertices; i++) {
      out << distance[i] << ' ';
    }
    out << endl;
  }
};

int main() {
  int n, m;
  ifstream in("bellmanford.in");
  in >> n >> m;
  graph G(n, m);
  G.read_neighbours(in);
  in.close();
  ofstream out("bellmanford.out");
  G.print_distances(out, 1);
  out.close();
  return 0;
}