#include <algorithm>
#include <climits>
#include <fstream>
#include <iostream>
#include <set>
#include <vector>

using namespace std;

#define MAXN 50001
#define MAXM 250000

long long d[MAXN];

struct edge {
    int u, v;
    long long w;
};

edge edges[MAXM];
int n, m;

int main() {
    // stuff
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");

    fin >> n >> m;
    for (int i = 2; i <= n; i++) d[i] = LONG_MAX;
    d[1] = 0;

    for (int i = 0; i < m; i++) {
        fin >> edges[i].u >> edges[i].v >> edges[i].w;
    }

    for (int k = 1; k < n; k++) {
        for (int i = 0; i < m; i++) {
            if (d[edges[i].v] > d[edges[i].u] + edges[i].w) {
                d[edges[i].v] = d[edges[i].u] + edges[i].w;
            }
        }
    }
    bool negative_cost = false;
    for (int i = 0; i < m; i++) {
        if (d[edges[i].v] > d[edges[i].u] + edges[i].w) {
            negative_cost = true;
            break;
        }
    }

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

    return 0;
}