#include <bits/stdc++.h>

using namespace std;

const int NMAX = 50001;
const int inf = NMAX * 1000;

int ans[NMAX];
int n, m, ciclu_negativ;
vector<vector<pair<int, int>>> a(NMAX);

void bellman_ford() {
    vector<int> viz(n + 1);
    queue<int> q;
    q.push(1);
    ans[1] = 0;
    while(!q.empty()) {
        int nod = q.front();
        q.pop();
        viz[nod]++;
        if(viz[nod] > n) {
            ciclu_negativ = 1;
            return;
        }
        for(auto &[i, cost] : a[nod]) {
            if(ans[i] > ans[nod] + cost) {
                ans[i] = ans[nod] + cost;
                q.push(i);
            }
        }
    }
}

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;
        a[x].push_back({y, c});
    }
    for(int i = 1; i <= n; i++)
        ans[i] = inf;

    bellman_ford();
    if(ciclu_negativ)
        cout << "Ciclu negativ!";
    else {
        for(int i = 2; i <= n; i++)
            cout << (ans[i] == inf ? -1 : ans[i]) << ' ';
    }
}