#include <fstream>
#include <vector>
#include <queue>
#include <cstdlib>

using namespace std;

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

#define NMAX 50005
#define INF ((1<<30)-1)

int n, m, d[NMAX], viz[NMAX];
vector<pair<int, int>> G[NMAX];
queue<pair<int, int>> q;

void citire() {
    f >> n >> m;
    int a, b, c;
    for (int i = 1; i <= m; i++) {
        f >> a >> b >> c;
        G[a].push_back({b, c});
    }
}

void initializare() {
    for (int i = 1; i <= n; i++)
        d[i] = INF;
}

void vizitare_nod(int x, int cost) {
    viz[x]++;
    if (viz[x] >= n) {
        g << "Ciclu negativ!";
        exit(0);
    }
    if (cost != d[x])
        return;
    for (auto &nod: G[x])
        if (d[x] + nod.second <= d[nod.first]) {
            d[nod.first] = d[x] + nod.second;
            q.push({nod.first, d[nod.first]});
        }
}

void BellmanFord() {
    d[1] = 0;
    viz[1] = 1;
    q.push({1, 0});
    while (!q.empty()) {
        pair<int, int> nod = q.front();
        q.pop();
        vizitare_nod(nod.first, nod.second);
    }
}

void afisare() {
    for (int i = 2; i <= n; i++)
        g << d[i] << ' ';
}

int main() {
    citire();
    initializare();
    BellmanFord();
    afisare();
    return 0;
}