#include <fstream>
#include <vector>
#include <queue>
#define DEFN 50010
#define DEFN 250010
#define INF 1 << 29

using namespace std;

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

queue < int > Q;

vector < pair < int, int > > L[DEFN];

int n, m, C[DEFN], F[DEFN], viz[DEFN];

int main () {
    fin >> n >> m;

    for (int i = 1; i <= m; ++ i) {
        int x, y, c;
        fin >> x >> y >> c;
        L[x].push_back (make_pair (y, c));
    }

    for (int i = 2; i <= n; ++ i) {
        C[i] = INF;
    }

    Q.push (1);
    F[1] = 1;
    viz[1] = 1;

    while (!Q.empty ()) {
        int nod = Q.front ();
        for (int i = 0; i < L[nod].size (); ++ i) {
            int new_nod = L[nod][i].first;
            int new_cost = L[nod][i].second;
            if (C[nod] + new_cost < C[new_nod]) {
                C[new_nod] = C[nod] + new_cost;
                ++ F[new_nod];
                if (F[new_nod] == n) {
                    fout << "Ciclu negativ!";
                    return 0;
                }
                if (!viz[new_nod]) {
                    Q.push (new_nod);
                    viz[new_nod] = 1;
                }
            }
        }
        Q.pop ();
        viz[nod] = 0;
    }

    for (int i = 2; i <= n; ++ i) {
        fout << C[i] << " ";
    }

    return 0;
}