#include <bits/stdc++.h>

const int INF = INT_MAX / 2;

struct Edge {
    int from, to, cost;
};

std::vector<Edge> edges;

int main() {
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    
    int n, m;
	std::cin >> n >> m;
    
    std::vector<std::vector<int>> D(n + 1, std::vector<int>(n + 1, INF));
    
    while(m--) {
        int x, y, z;
        std::cin >> x >> y >> z;
        edges.push_back({x, y, z});
    }
    
    int start = 1;
    std::vector<int> dist(n + 1, INF);
    dist[start] = 0;

    for(int i = 1; i <= n; ++i) {
        for(const auto& edge : edges) {
            if(dist[edge.from] != INF) {
                dist[edge.to] = std::min(dist[edge.to], dist[edge.from] + edge.cost);
            }
        }
    }

    for(const auto& edge : edges) {
        if(dist[edge.from] != INF && dist[edge.to] > dist[edge.from] + edge.cost) {
            std::cout << "Ciclu negativ!";
            break;
        }
    }

    for(int i = 2; i <= n; ++i) {
        std::cout << dist[i] << ' ';
    }
    
    return 0;
}