#include <bits/stdc++.h>

using namespace std;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
int n;
const int inf = 0x3f3f3f3f;

//  Nod, cost
vector<pair<int, int>> vec[50002];
long long dist[50002];
unordered_set<int> current_queue;
int viz[50002];

void bellmanford (int start) {
    queue<int> q;
    q.push(start);
    current_queue.insert(start);

    dist[start] = 0;

    while (!q.empty()) {
        int front = q.front();
        q.pop();
        current_queue.erase(front);

        viz[front]++;
        if (viz[front] >= n) {
            out << "Ciclu negativ!";
            exit(0);
        }

        for (auto [n, c] : vec[front]) {
            if (dist[n] > dist[front] + c) {
                if (!current_queue.count(n)) {
                    current_queue.insert(n);
                    q.push(n);
                }
                dist[n] = dist[front] + c;
            }
        }
    }
}

int main () {
    int m;
    in >> n >> m;

    fill(dist, dist + n + 1, inf);

    for (int i = 0; i < m; ++i) {
        int a, b, c;
        in >> a >> b >> c;
        vec[a].push_back({b, c});
    }

    bellmanford(1);

    for (int i = 2; i <= n; ++i) {
        out << dist[i] << ' ';
    }

    return 0;
}