#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
const char nl = '\n';
const char sp = ' ';
const int inf = 0x3f3f3f3f;
const int mod = 666013;
const char out[2][4]{ "NO", "YES" };
#define all(a) a.begin(), a.end()
using ll = long long;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const int nmax = 5e4;
int n, m;
struct edge {
    int u, v, w;
};
vector<edge> edges;
ll dist[nmax + 5]{ 0 };

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    fin >> n >> m;
    edges.reserve(m);
    for (int i = 1; i <= m; ++i) {
        edge e;
        fin >> e.u >> e.v >> e.w;
        edges.push_back(e);
    }
    for (int i = 1; i <= n; ++i) {
        dist[i] = 1e18;
    }
    dist[1] = 0;
    for (int t = 1; t < n; ++t) {
        for (auto& e : edges) {
            dist[e.v] = min(dist[e.v], dist[e.u] + e.w);
        }
    }
    for (auto& e : edges) {
        if (dist[e.u] + e.w < dist[e.v]) {
            fout << "Ciclu negativ!";
            return 0;
        }
    }
    for (int i = 2; i <= n; ++i) {
        fout << dist[i] << sp;
    }
}