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

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

void bellman(ostream &cout) {
    for (int i = 1; i <= n; ++i) {
        dist[i] = 0x3f3f3f3f;
    }
    dist[1] = 0;
    q.push({0, 1});
    while(!q.empty()) {
        int node = q.top().second;
        q.pop();
        ++viz[node];
        if (viz[node] >= n) {
            cout << "Ciclu negativ!";
            exit(0);
        }
        for (int j = 0; j < v[node].size(); ++j) {
            if (v[node][j].first + dist[node] < dist[v[node][j].second]) {
                dist[v[node][j].second] = v[node][j].first + dist[node];
                q.push({dist[v[node][j].second], v[node][j].second});
            }
        }
    }
}

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({c, y});
    }
    bellman(cout);
    for (int i = 2; i <= n; ++i) {
        cout << dist[i] << " ";
    }
}