#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

typedef pair<int, int> Edge;

int n, m, d[50001];
bool better[50001];
vector<Edge> g[50001];
const int INF = 50e6;


int main() {

    ifstream in("bellmanford.in");
    ofstream out("bellmanford.out");
    in >> n >> m;
    for (int i = 1, x, y, c; i <= m; ++i) {
        in >> x >> y >> c;
        g[x].push_back({c, y});
    }

    for (int i = 1; i <= n; ++i) {
        d[i] = INF;
    }

    d[1] = 0;
    better[1] = true;


    bool changed = true;
    int k, x, i, y, size, sum;

    for (k = 1; k < n; ++k) {
        changed = false;
        for (x = 1; x <= n; ++x) {
            if (d[x] == INF || !better[x]) continue;
            size = g[x].size();
            for (i = 0; i < size; ++i) {
                y = g[x][i].second;
                sum = d[x] + g[x][i].first;
                if (sum < d[y]) {
                    d[y] = sum;
                    better[y] = true;
                    changed = true;
                }
            }
            better[x] = false;
        }

        if (!changed) break;
    }

    if (k == n) {
        for (int x = 1; x <= n; ++x) {
            if (d[x] == INF) continue;
            if (!better[x]) continue;
            for (int i = 0; i < g[x].size(); ++i) {
                int y = g[x][i].second;
                if (d[x] + g[x][i].first < d[y]) {
                    out << "Ciclu negativ!";
                    return 0;
                }
            }
        }
    }


    for (int i = 2; i <= n; ++i) {
        out << d[i] << " ";
    }

    return 0;
}