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

#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) {
    queue<int> nodes;
    vector<bool> pushed(vertices);
    vector<int> pushed_nr(vertices, 0);
    distance[src] = 0;
    nodes.push(src);
    pushed[src] = true;

    while (!nodes.empty()) {
      auto v1 = nodes.front();
      nodes.pop();
      pushed[v1] = false;
      if (++pushed_nr[v1] == vertices) {
        return -1;
      }
      for (auto v2 : adj[v1]) {
        if (distance[v1] + v2.second < distance[v2.first]) {
          distance[v2.first] = distance[v1] + v2.second;
          if (!pushed[v2.first]) {
            nodes.push(v2.first);
            pushed[v2.first] = true;
          }
        }
      }
    }
    
    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;
}