#include <stdio.h>
#include<vector>
#include<queue>
#include<limits.h>

using namespace std;

typedef std::pair<int, int> edge;

std::vector<int> bellman_ford(const std::vector<std::vector<edge> >& graph, const int source) {
    vector<int> dist(graph.size(), INT_MAX);
    vector<int> visited(graph.size(), 0);
    queue<int> q;
    q.push(source);  // add source to the queue
    dist[source] = 0;  // make the distance to source 0

    while(!q.empty()) {
        // get the first node in queue and remove it
        int current = q.front();
        q.pop();
        if(visited[current]) {
            // negative cycle
            return std::vector<int>();
        } else {
            visited[current] = 1;
        }

        // loop through its neighbors to recalculate the distances
        for(int i = 0; i < graph[current].size(); i++) {
            int neighbor = graph[current][i].first;
            int weight = graph[current][i].second;
            // if we found a better distance, update it and add the node in the queue
            if (dist[neighbor] > dist[current] + weight) {
                dist[neighbor] = dist[current] + weight;
                q.push(neighbor);
            }
        }
    }

    return dist;
}

int main() {
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    int n, m, src, dst, weight;
    scanf("%d%d", &n, &m);

    std::vector<std::vector<edge> > graph(n);

    for(int i = 0; i < n; i++) {
        scanf("%d%d%d", &src, &dst, &weight);
        graph[src - 1].push_back(make_pair(dst - 1, weight));
    }
    vector<int> dist;
    dist = bellman_ford(graph, 0);


    if(dist.size() == 0) printf("Ciclu negativ!\n");
    else {
        for(int i = 1; i < dist.size(); i++)
            printf("%d ", dist[i]);
        printf("\n");
    }

    return 0;
}