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

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

#define inf 1e9

struct Muchie {int x, y, cost;};

typedef vector<vector<int>> ListaVecini;
typedef vector<vector<int>> ListaCosturi;


vector<int> BellmanFord(int n, int start, ListaVecini &vecin, ListaCosturi &cost, vector<int> &tata) {

    queue<int> Q;
    vector<bool> in_queue(n, false);
    vector<int> dist(n, inf);
    vector<int> lung(n, 0);

    Q.push(start);
    in_queue[start] = true;
    dist[start] = 0;
    tata[start] = -1;

    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        in_queue[u] = false;

        for (int i = 0; i < vecin[u].size(); i++) {
            int v = vecin[u][i];
            int c = cost[u][i];

            if (dist[u] < inf && dist[u] + c < dist[v]) {
                lung[v] = lung[u] + 1;
                tata[v] = u;
                dist[v] = dist[u] + c;

                if (!in_queue[v]) {
                    Q.push(v);
                    in_queue[v] = true;
                }

                if (lung[v] >= n) // Ciclu negativ;
                    return {-1};
            }
        }
    }
    return dist;
}

int main() {

    int n, m;
    in >> n >> m;

    ListaVecini vecin(n);
    ListaCosturi cost(n);

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

        vecin[x].push_back(y);
        cost[x].push_back(c);
    }

    vector<int> tata(n);
    vector<int> dist = BellmanFord(n, 0, vecin, cost, tata);

    if (dist.size() == 1 && dist[0] == -1) {
        out << "Ciclu negativ!\n";
    }
    else {
        for (int i = 1; i < n; i++)
            out << dist[i] << " ";
        out << "\n";
    }
    return 0;
}