#include <bits/stdc++.h>

using namespace std;

#if 1
    #define pv(x) cout<<#x<<" = "<<(x)<<"; ";cout.flush()
    #define pn cout<<endl
#else
    #define pv(x)
    #define pn
#endif

#ifdef INFOARENA
    ifstream in("bellmanford.in");
    ofstream out("bellmanford.out");
#else
    #define in cin
    #define out cout
#endif

using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
#define pb push_back
#define mp make_pair
const int NMax = 3e6 + 5;
const ll inf_ll = 1e18 + 5;
const int inf_int = 1e9 + 5;
const int mod = 100003;
using zint = int;

int main() {
    cin.sync_with_stdio(false);
    cin.tie(0);

    int N,M;
    in >> N >> M;
    vector< vector<pair<int,int>> > v(N+1);
    vector< int > dist(N+1, inf_int);
    dist[1] = 0;
    for (int i = 1; i <= M; ++i) {
        int x,y,c;
        in >> x >> y >> c;

        v[x].pb( {y,c} );
        // v[y].pb( {x,c} );
    }

    bool update = true;
    int c;
    for (c = 1; c <= N; ++c) {

        update = false;
        for (int i = 1; i <= N; ++i) {
            for (auto p : v[i]) {
                int nxt = p.first, cost = p.second;
                if (dist[nxt] > dist[i] + cost) {
                    dist[nxt] = dist[i] + cost;
                    update = true;
                }
            }
        }

        if (!update) {
            break;
        }
    }

    if (update) {
        out << "Ciclu negativ!";
    }
    else {
        for (int i = 2; i <= N; ++i) {
            out << dist[i] << ' ';
        }
    }

    return 0;
}