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

using namespace std;

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

const int DIM = 50005;
const int INF = 1e9;

int n, m, x, y, c;
bool ciclu_negativ = false;
vector<vector<pair<int, int>>> g(DIM);
vector<int> dis(DIM, INF), viz(DIM);

void read() {
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        fin >> x >> y >> c;
        g[x].push_back({y, c});
    }
}

void bellman_ford() {
    queue<int> coada;

    dis[1] = 0;
    coada.push(1);

    while (!coada.empty() && !ciclu_negativ) {
        int cur = coada.front();
        coada.pop();
        viz[cur]++;

        if (viz[cur] == n) {
            ciclu_negativ = true;
            return;
        }

        for (const auto& j: g[cur]) {
            int vecin = j.first;
            int cost = j.second;

            if (dis[vecin] > dis[cur] + cost) {
                dis[vecin] = dis[cur] + cost;
                coada.push(vecin);
            }
        }
    }
}

void write() {
    if (!ciclu_negativ) {
        for (int i = 2; i <= n; i++)
            fout << dis[i] << " ";
    }
    else
        fout << "Ciclu negativ!\n";
}

int main(void) {
    read();
    bellman_ford();
    write();

    fin.close();
    fout.close();
    return 0;
}