#include <fstream>
#include <queue>

constexpr int MAX_N = 50001, MAX_M = 250001, INF = 0x7fffffff;

int n, m, start[MAX_M], at[MAX_M], costs[MAX_M], next[MAX_M], count;

std::queue<int> q;
bool inq[MAX_M];
int d[MAX_N], nrq[MAX_N];

inline void add(int from, int to, int cost) {
    ++count;
    at[count] = to;
    costs[count] = cost;
    next[count] = start[from];
    start[from] = count;
}

int main() {
    std::ifstream in("bellmanford.in");
    std::ofstream out("bellmanford.out");
    int i, x, y, cost;
    in >> n >> m;
    for (i = 1; i <= m; ++i) {
        in >> x >> y >> cost;
        d[i] = INF;
        add(x, y, cost);
    }
    q.push(1);
    d[1] = 0;
    inq[1] = true;
    ++nrq[1];
    while (!q.empty()) {
        x = q.front();
        q.pop();
        inq[x] = false;
        for (int p = start[x]; p != 0; p = next[p]) {
            y = at[p];
            cost = costs[p];
            if (d[x] + cost < d[y]) {
                d[y] = d[x] + cost;
                if (!inq[y]) {
                    inq[y] = true;
                    q.push(y);
                    if (++nrq[y] >= n) {
                        out << "Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
    }
    for (i = 2; i <= n; ++i) out << d[i] << ' ';
    return 0;
}