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

struct Edge {
    Edge(int other = 0, int cost = 0) : other(other), cost(cost) {}
    int other, 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< vector<Edge> > edges(n, vector<Edge>());
    for (int i = 0; i < m; ++i) {   
        int from, to, cost;
        cin >> from >> to >> cost;
        from--; to--;
        edges[from].emplace_back(to, cost);
    }
    
    vector< int > cst(n, 0x3f3f3f3f);
    cst[0] = 0;
    queue< int > que; que.push(0);
    vector< bool > in_que(n, false);
    vector< int > ap(n, 0);
    
    while (!que.empty()) {
        int node = que.front();
        que.pop();
        in_que[node] = false;
        for (auto&& edge : edges[node])
            if (cst[edge.other] > cst[node] + edge.cost) {
                cst[edge.other] = cst[node] + edge.cost;
                ++ap[edge.other];
                if (ap[edge.other] == n) {
                    cout << "Ciclu negativ!\n";
                    return 0;
                }
                if (!in_que[edge.other])
                    que.push(edge.other);
                in_que[edge.other] = true;
            }
    }
    
    for (int i = 1; i < n; ++i)
        cout << cst[i] << " \n"[i == n-1];
    
    return 0;
}

//Trust me, I'm the Doctor!