#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 5e4 + 5;
const int INF = 0x3f3f3f3f;

int n, m;
bool negative_cycle;
int dist[N_MAX], counter[N_MAX];
vector <pair <int, int>> graph[N_MAX];
bitset <N_MAX> in_q;
queue <int> q;

void read() {
    ifstream fin("bellmanford.in");

    int x, y, c;

    fin >> n >> m;
    while (m--) {
        fin >> x >> y >> c;
        graph[x].emplace_back(y, c);
    }

    fin.close();
}

inline void solve() {
    int node, new_dist;

    memset(dist, INF, sizeof dist);
    dist[1] = 0;
    q.push(1);
    in_q.set(1);
    counter[1] = n  - 1;

    while (!q.empty() && !negative_cycle) {
        node = q.front();
        q.pop();
        in_q.reset(node);

        for (const auto &son : graph[node]) {
            new_dist = dist[node] + son.second;
            if (new_dist < dist[son.first]) {
                dist[son.first]= new_dist;
                if (!in_q[son.first]) {
                    q.push(son.first);
                    in_q.set(son.first);
                    ++counter[son.first];
                    if (counter[son.first] == n) {
                        negative_cycle = true;
                    }
                }
            }
        }
    }
}

void write() {
    ofstream fout("bellmanford.out");

    if (negative_cycle) {
        fout << "Ciclu negativ";
    } else {
        for (int i = 2; i <= n; ++i) {
            fout << dist[i] << " ";
        }
    }

    fout.close();
}

int main() {
    read();
    solve();
    write();
    return 0;
}