#include <bits/stdc++.h>
#define ll long long
#define nl '\n'
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define F0R(i, a, b) for (int i = a; i >= b; --i)
#define FORd(i, n) for (int i = 0; i < n; ++i)
#define F0Rd(i, n) for (int i = n - 1; i >= 0; --i)
#define trav(a, x) for (auto &a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mxN = 5e4 + 5, INF = 1e9 + 7;

int n, m, dist[mxN];
vector<pair<int, pair<int, int>>> muchii;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

void solve() {
    fin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        dist[i] = INF;
    }
    while (m--) {
        int x, y, z;
        fin >> x >> y >> z;
        muchii.push_back(make_pair(x, make_pair(y, z)));
    }
    dist[1] = 0;
    for (int i = 1; i <= n - 1; ++i) {
        for (auto elem : muchii) {
            int first_node = elem.first;
            int second_node = elem.second.first;
            int new_cost = elem.second.second;
            dist[second_node] = min(dist[second_node], dist[first_node] + new_cost);
        }
    }
    //check negative cycle
    for (auto elem : muchii) {
        int first_node = elem.first;
        int second_node = elem.second.first;
        int new_cost = elem.second.second;
        if (dist[second_node] > dist[first_node] + new_cost) {
            fout << "Ciclu negativ!";
            return;
        }
    }
    for (int i = 2; i <= n; ++i) {
        fout << dist[i] << " ";
    }
}

int main() {
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(0);
    int T = 1;
//  cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

//read the question correctly (ll vs int)
//what's the meaning of the problem ? Think outside the BOX !!!
//edge cases ?
//make it simple
//write everything (observations, edge cases, ideas, steps, methods, ...)