#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>

struct Edge {
    int start;
    int end;
    int cost;
};

int main() {
    FILE *in = fopen("bellmanford.in", "r");
    FILE *out = fopen("bellmanford.out", "w");
    int nodes, edges;
    std::vector<Edge> graphEdges;

    fscanf(in, "%d %d", &nodes, &edges);

    for (int i = 0; i < edges; i++) {
        int x, y, cost;
        Edge e;
        fscanf(in, "%d %d %d", &x, &y, &cost);
        e.start = x - 1;
        e.end = y - 1;
        e.cost = cost;

        graphEdges.push_back(e);
    }

    int source = 0;
    std::vector<int> distances;

    for (int i = 0; i < nodes; i++) {
        distances.push_back(INT32_MAX);
    }

    distances[source] = 0;

    for (int i = 0; i < nodes - 1; i++) {
        for (auto element : graphEdges) {
            int start = element.start;
            int end = element.end;
            int cost = element.cost;

            if (distances[start] + cost < distances[end]) {
                distances[end] = distances[start] + cost;
            }
        }
    }

    bool show = true;

    for (auto element : graphEdges) {
        int start = element.start;
        int end = element.end;
        int cost = element.cost;

        if (distances[start] + cost < distances[end]) {
            fprintf(out, "Ciclu negativ!");
            show = false;
            break;
        }
    }

    if (show) {
        for (int i = 1; i < nodes; i++) {
            fprintf(out, "%d ", distances[i]);
        }
    }

    fclose(in);
    fclose(out);

    return 0;
}