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

struct Graph{
public:
    int size;
    std::vector<std::vector<std::pair<int,int>>> elements;

    Graph(int size){
        this->size = size;
        std::vector<std::pair<int,int>> temp;

        for(int i = 0; i < size; i++) {
            elements.push_back(temp);
        }
    }

    void addEdge(int start, int end, int cost) {
        elements[start].push_back({end,cost});
    }

    int getCost(int start, int end) {
        int i = 0;
        for(i = 0; i < elements[start].size(); i++) {
            if(elements[start][i].first == end) {
                break;
            }
        }
        return elements[start][i].second;
    }
};

int main() {
    FILE *in = fopen("bellmanford.in","r");
    FILE *out = fopen("bellmanford.out","w");
    int nodes,edges;

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

    Graph graph(nodes);

    for(int i = 0; i < edges; i++) {
        int x,y,cost;
        fscanf(in,"%d %d %d",&x,&y,&cost);
        graph.addEdge(x - 1,y - 1,cost);
    }

    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(int j = 0; j < nodes; j++) {
            for(std::pair<int,int> element : graph.elements[j]) {
                int start = j;
                int end = element.first;
                int cost = element.second;

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

    bool show = true;

    for(int j = 0; j < nodes; j++) {
        for(std::pair<int,int> element : graph.elements[j]) {
            int start = j;
            int end = element.first;
            int cost = element.second;

            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;
}