#include <iostream>
#include <vector>
#include <utility>
#include <climits>
using namespace std;

#define NMAX 50000

int n;
vector<pair<int, int>> g[NMAX + 1];
int dist[NMAX + 1];

void read() {
    int m;
    cin >> n >> m;
    while (m--) {
        int x, y, c;
        cin >> x >> y >> c;
        g[x].push_back({y, c});
    }
}

void bellman_ford() {
    for (int i = 1; i <= n; i++) {
        dist[i] = INT_MAX;
    }
    dist[1] = 0;

    for (int i = 0; i < n; i++) {
        for (int nod = 1; nod <= n; nod++) {
            for (auto muchie : g[nod]) {
                if (dist[muchie.first] > dist[nod] + muchie.second) {
                    dist[muchie.first] = dist[nod] + muchie.second;
                }
            }
        }
    }

    for (int nod = 1; nod <= n; nod++) {
        for (auto muchie : g[nod]) {
            if (dist[muchie.first] > dist[nod] + muchie.second) {
                cout << "Ciclu negativ!";
                exit(0);
            }
        }
    }
}

void afis() {
    for (int i = 2; i <= n; i++) {
        cout << dist[i] << ' ';
    }
}

int main() {
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);

    read();
    bellman_ford();
    afis();

    return 0;
}