#include <bits/stdc++.h>

#include <bits/stdc++.h>

std::ifstream in("bellmanford.in");
std::ofstream out("bellmanford.out");

template<typename T>
using Vec = std::vector<T>;
template<typename T, typename U>
using Pair = std::pair<T, U>;
template<typename F>
using Func = std::function<F>;
using i64 = int64_t;
using u64 = uint64_t;
using i8 = char;
using u8 = unsigned char;
template<typename T>
T update_min(T &min, T val) {
    return min = std::min(min, val);
}
template<typename T>
T update_max(T &max, T val) {
    return max = std::max(max, val);
}
template<typename T>
using Lim = std::numeric_limits<T>;

constexpr int N = 5e4 + 1, M = 25e4 + 1;

int n, m;
struct Edge {
    int v, c;
};
Vec<Edge> g[N];
bool queued[N];
int d[N];
int cnt[N];

void solve() {
    std::queue<int> q{{1}};
    queued[1] = true;
    std::fill(d + 2, d + n + 1, Lim<int>::max());
    bool ok = true;
    while (!q.empty() && ok) {
        int u = q.front();
        q.pop();
        queued[u] = false;
        for (auto e : g[u]) {
            int c = d[u] + e.c;
            if (c < d[e.v]) {
                d[e.v] = c;
                if (!queued[e.v]) {
                    if (cnt[e.v] == n - 1) {
                        ok = false;
                        break;
                    }
                    ++cnt[e.v];
                    queued[e.v] = true;
                    q.push(e.v);
                }
            }
        }
    }
    if (!ok) {
        out << "Ciclu negativ!\n";
        return;
    }
    for (int i = 2; i <= n; ++i) {
        out << d[i] << ' ';
    }
    out << '\n';
}

int main() {
    in >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v, c;
        in >> u >> v >> c;
        g[u].push_back({v, c});
    }
    solve();
}