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

#define INF 1e9

using namespace std;


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

vector<vector<pair<int, int>>> la;
vector<int> viz;
vector<int> tata;
vector<int> d;
vector<int> lung;
bool areCiclu;
queue<int> q;

void bellmanFord(int s, int N) {
    d.assign(N + 1, INF);
    tata.assign(N + 1, 0);
    viz.assign(N + 1, 0);
    lung.assign(N + 1, 0);

    d[s] = 0;
    q.push(s);
    viz[s] = 1;

    while (!q.empty()) {
        int crt = q.front();
        q.pop();
        viz[crt] = 0;

        for (auto& vecin : la[crt]) {
            int cost = vecin.first;
            int nod = vecin.second;

            if (d[crt] != INF && d[crt] + cost < d[nod]) {
                d[nod] = d[crt] + cost;
                tata[nod] = crt;

                if (viz[nod] == 0) {
                    viz[nod] = 1;
                    q.push(nod);
                }

                lung[nod] = lung[crt] + 1;
                if (lung[nod] > N - 1) {
                    areCiclu = true;
                    break;
                }
            }
        }

    }
}

int main() {

    int N, M;
    fin >> N >> M;

    la.resize(N + 1);

    for (int i = 0; i < M; i++) {
        int x, y, w;
        fin >> x >> y >> w;
        la[x].push_back({w, y});
    }

    bellmanFord(1, N);

    if (areCiclu) { 
        fout << "Ciclu negativ!"; 
    } else {
        for (int i = 2; i <= N; i++) {
            fout << d[i] << ' ';
        }
    }

    return 0;
}