#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define ll long long
#define INF 1000000000
#define MOD 666013

const int NMAX = 5e4;

vector <pair<int, int>> g[NMAX + 5];
int dist[NMAX + 5];
bool inq[NMAX + 5];
queue <int> q;

int main() {
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");
    ios::sync_with_stdio(false), fin.tie(0);
    int n, m;
    fin >> n >> m;
    for (int i = 1, a, b, c; i <= m; i++) {
        fin >> a >> b >> c;
        g[a].pb({b, c});
    }

    for (int i = 2; i <= n; i++) dist[i] = INT_MAX;

    dist[1] = 0;
    q.push(1);
    inq[1] =  true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto x: g[u]) {
            if (dist[u] + x.second < dist[x.first]) dist[x.first] = dist[u] + x.second;
            if (!inq[x.first]) {
                inq[x.first] = true;
                q.push(x.first);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (dist[i] == INT_MAX) {
            fout << "Ciclu Negativ";
            return 0;
        }
    }

    for (int i = 2; i <= n; i++) fout << dist[i] << " ";
    return 0;
}