#include <bits/stdc++.h>

using namespace std;

const int nmax = static_cast<int>(5e4+1);
const int INF = 1 << 30;
struct edge_t {
    int node, cost;
};
vector<edge_t> graph[nmax];
int n;
int dist[nmax];
bitset<nmax> in_queue;
int queue_cnt[nmax];
queue<int> q;

int main() {
    freopen("carici.in", "r", stdin);

    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);

    int m;
    scanf("%d%d", &n, &m);

    for (int i = 0, x, y, z; i < m ; i++) {
        scanf("%d%d%d", &x, &y, &z);
        graph[x].push_back({y, z});
    }

    for (int i = 0; i <= n; i++) dist[i] = INF;
    dist[1] = 0;

    bool negative_cycles = false;
    q.push(1);
    in_queue[1] = true;

    while (!q.empty() && !negative_cycles) {
        int node = q.front();
        q.pop();
        in_queue[node] = false;

        if (dist[node] == INF) continue;
        for (auto &next_edge: graph[node]) {
            if (dist[next_edge.node] > dist[node] + next_edge.cost) {
                dist[next_edge.node] = dist[node] + next_edge.cost;

                if (!in_queue[next_edge.node]) {
                    if (queue_cnt[next_edge.node] > n) {
                        negative_cycles = true;
                    } else {
                        in_queue[next_edge.node] = true;
                        queue_cnt[next_edge.node]++;
                        q.push(next_edge.node);
                    }
                }
            }
        }
    }

    if (!negative_cycles) {
        for (int i = 2; i <= n; i++) {
            cout << dist[i] << " ";
        }
        cout << "\n";
    } else {
        cout << "Ciclu negativ!\n";
    }

    return 0;
}