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

using namespace std;

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

struct Edge {
    int u, v, c;
};

typedef vector<vector<Edge>> Graph;

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

Graph readGraph() {
    ifstream in(IN_FILE);
    int V, E;
    in >> V >> E;
    auto graph = Graph(V);
    for (int i = 0; i < E; i++) {
        int u, v, c;
        in >> u >> v >> c;
        graph[u - 1].push_back({u - 1, v - 1, c});
    }
    in.close();
    return graph;
}

void writeOutput(const vector<int>& distances, const int source) {
    ofstream out(OUT_FILE);
    if (distances.empty()) {
        out << "Ciclu negativ!\n";
    } else {
        for (int u = 0; u < int(distances.size()); u++) {
            if (u != source) {
                out << distances[u] << " ";
            }
        }
        out << "\n";
    }
    out.close();
}

int main() {
    const auto graph = readGraph();
    const int source = 0;
    const auto distances = bellmanFord(graph, source);
    writeOutput(distances, source);
    return 0;
}