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

using namespace std;

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

public:
  graph(int n, int m) : vertices(n), edges(m), adjacency(n + 1), distance(n + 1, n + 1), pred(n + 1, 0) {};
  void read_adj(ifstream& in) {
    int e1, e2, w;
    for (int j = 0; j < edges; j++) {
      in >> e1 >> e2 >> w;
      adjacency[e1].push_back(make_pair(e2, w));
    }
  }
  int bellman_ford(int src) {
    distance[src] = 0;
    for (int i = 1; i <= vertices - 1; i++) {
      for (int e1 = 1; e1 <= vertices; e1++) {
        for (auto e2 : adjacency[e1]) {
    //      cout << e1 << " " << e2.first << endl;
    //      cout << "\tComparing " << distance[e2.first] << " and " << distance[e1] + e2.second << endl;
          if (distance[e2.first] > distance[e1] + e2.second) {
    //        cout << "\tChanging values" << endl;
            distance[e2.first] = distance[e1] + e2.second;
            pred[e2.first] = e1;
    //        cout << "\tChanged values" << endl;
          }
        }
      }
    }
    for (int i = 1; i <= vertices - 1; i++) {
      for (int e1 = 1; e1 <= vertices; e1++) {
        for (auto e2 : adjacency[e1]) {
          if (distance[e2.first] > distance[e1] + e2.second) {
            return -1;
          }
        }
      }
    }
    return 0;
  }
  void print_bellman(ostream& out) {
    if (bellman_ford(1) == -1) {
      out << "Ciclu negativ!" << endl;
      return;
    }
    for (int i = 2; i <= vertices; i++) {
      out << distance[i] << ' ';
    }
    out << endl;
  }
};

int main() {
  int n, m;
  ifstream in("bellmanford.in");
  ofstream out("bellmanford.out");
  in >> n >> m;
  graph G(n, m);
  G.read_adj(in);
  G.print_bellman(out);
  return 0; 
}