#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, vector<Muchie> muchii, vector<int> &tata) {
    vector<int> dist(n, inf);
    dist[start] = 0;
    tata[start] = -1;

    bool changed;

    for (int i = 0; i < n; i++) {
        changed = false;

        for (const Muchie& m : muchii) {
            if (dist[m.x] != inf && dist[m.x] + m.cost < dist[m.y]) {
                changed = true;
                dist[m.y] = dist[m.x] + m.cost;
                tata[m.y] = m.x;
            }
        }

        if (!changed)
            break;
        if (i == n -1 && changed)
            return {-1};
    }

    return dist;
}

int main() {

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

    vector<Muchie> muchii(m);
    for (int i = 0; i < m; i++) {
        in >> muchii[i].x >> muchii[i].y >> muchii[i].cost;
        muchii[i].x--; muchii[i].y--;
    }

    vector<int> tata(n);
    vector<int> dist = BellmanFord(n, 0, muchii, 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;
}