#include <fstream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>

using namespace std;

const string IN_FILE = "bellmanford.in";
const string OUT_FILE = "bellmanford.out";
const int INF = 0x3f3f3f3f;

typedef pair<int, int> Edge;
typedef vector<vector<Edge>> Graph;

vector<int> bellmanFord(const Graph& graph, const int source) {
    const int size = int(graph.size());
    queue<int> q;
    auto inQ = vector<bool>(size, false);
    auto distances = vector<int>(size, INF);
    auto relaxedCount = vector<int>(size, 0);
    q.push(source);
    inQ[source] = true;
    distances[source] = 0;
    while (!q.empty()) {
        const int v = q.front();
        q.pop();
        inQ[v] = false;
        if (relaxedCount[v]++ > size) {
            return vector<int>();
        }
        for (const auto& e : graph[v]) {
            if (distances[v] + e.second < distances[e.first]) {
                if (!inQ[e.first]) {
                    q.push(e.first);
                    inQ[e.first] = true;
                }
                distances[e.first] = distances[v] + e.second;
            }
        }
    }
    return distances;
}

Graph read() {
    ifstream in(IN_FILE);
    int nodes, edges;
    in >> nodes >> edges;
    auto graph = Graph(nodes);
    for (int i = 0; i < edges; i++) {
        int v, w, c;
        in >> v >> w >> c;
        graph[v - 1].push_back(Edge(w - 1, c));
    }
    in.close();
    return graph;
}

void print(const vector<int>& distances) {
    ofstream out(OUT_FILE);
    if (distances.empty()) {
        out << "Ciclu negativ!\n";
    } else {
        for (int i = 1; i < int(distances.size()); i++) {
            out << distances[i] << (i + 1 < int(distances.size()) ? " " : "\n");
        }
    }
    out.close();
}

int main() {
    const auto graph = read();
    const auto distances = bellmanFord(graph, 0);
    print(distances);
    return 0;
}