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

int n, m, dist[50001];
vector<vector<pair<int, int> > > v(50001);

int main() {
    ifstream cin("bellmanford.in");
    ofstream cout("bellmanford.out");
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y, c;
        cin >> x >> y >> c;
        v[x].push_back({y, c});
    }
    for (int i = 2; i <= n; ++i) {
        dist[i] = 0x3f3f3f3f;
    }
    dist[1] = 0;
    for (int k = 1; k <= n - 1; ++k) {
        bool changed = false;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < v[i].size(); ++j) {
                if (dist[i] + v[i][j].second < dist[v[i][j].first]) {
                    dist[v[i][j].first] = dist[i] + v[i][j].second;
                    changed = true;
                }
            }
        }
        if (changed == false) {
            for (int i = 2; i <= n; ++i) {
                cout << dist[i] << " ";
            }
            return 0;
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < v[i].size(); ++j) {
            if (dist[i] + v[i][j].second < dist[v[i][j].first]) {
                cout << "Ciclu negativ!";
                return 0;
            }
        }
    }
    for (int i = 2; i <= n; ++i) {
        cout << dist[i] << " ";
    }
}