#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int first, second, cost;
};

int main() {
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    
    int n, m; cin >> n >> m;
    vector< Edge > edges(m);
    for (int i = 0; i < m; ++i) {   
        cin >> edges[i].first >> edges[i].second >> edges[i].cost;
        edges[i].first--, edges[i].second--;
    }
        
    vector< int > old_cost(n, 0x3f3f3f3f);
    old_cost[0] = 0;
    auto new_cost = old_cost;
    for (int i = 0; i <= n; ++i) {
        for (auto&& edge : edges) {
            if (new_cost[edge.second] > old_cost[edge.first] + edge.cost)
                new_cost[edge.second] = old_cost[edge.first] + edge.cost;
        }
        if (i == n && old_cost != new_cost) {
            cout << "Ciclu negativ!\n";
            return 0;
        }
        old_cost = new_cost;
    }
    
    for (int i = 1; i < n; ++i) 
        cout << old_cost[i] << " \n"[i == n-1];
    
    return 0;
}

//Trust me, I'm the Doctor!