#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 50005;
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 bellmanford(int node, int cost) {
    if (cost < dist[node]) {
        dist[node] = cost;
        if (!in_q[node]) {
            q.push(node);
            in_q.set(node);
            ++counter[node];
            if (counter[node] == n) {
                negative_cycle = true;
            }
        }
    }
}

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]) {
           bellmanford(son.first, dist[node] + son.second);
        }
    }
}

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;
}