#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <bitset>
#include <climits>

using namespace std;

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


int n;

struct edge {
    int y;
    int c;
};

struct edge_comp {
    bool operator()(const edge &e1, const edge &e2) {
        return e1.c > e2.c;
    }
};

int main() {
    int m;

    in >> n >> m;

    vector<vector<edge> > graph(n + 1);
    vector<int> d(n + 1, INT_MAX);
    vector<int> times_selected(n + 1, 0);
    bitset<50005> in_queue(false);
    queue<int> q;
    bool negative_cycle = false;

    for (int i = 0; i < m; ++i) {
        int x, y, c;

        in >> x >> y >> c;

        edge e = {y, c};

        graph[x].push_back(e);
    }

    d[1] = 0;
    q.push(1);
    in_queue[1] = true;

    while (!q.empty() && !negative_cycle) {
        int node = q.front();
        
        q.pop();
        in_queue[node] = false;

        for (vector<edge>::iterator e = graph[node].begin(); e != graph[node].end(); ++e) {
            if (d[e->y] > d[node] + e->c) {
                d[e->y] = d[node] + e->c;

                if (!in_queue[e->y]) {
                    if (times_selected[e->y] > n) {
                        negative_cycle = true;
                    } else {
                        q.push(e->y);
                        times_selected[e->y] += 1;
                        in_queue[e->y] = true;
                    }
                }
            }
        }
    }

    if (negative_cycle) {
        out << "Ciclu negativ!\n";
        return 0;
    }

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

    out << '\n';

    return 0;
}