#include <fstream>
#include <vector>
using namespace std;

ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");

const int inf = (1 << 31) - 1;
vector<pair<int, pair<int, int>>> muchii;
vector<int> dist;


void bellman_ford(int n, int m, int s) {
    dist[s] = 0;
    for(int i = 1; i < n; i++) {
        for(auto m: muchii) {
            int x = m.second.first;
            int y = m.second.second;
            int w = m.first;
            if(dist[x] != inf && dist[y] > dist[x] + w) {
                dist[y] = dist[x] + w;
            }
        }
    }

    bool ciclu_negativ = false;
    for(auto m: muchii) {
        int x = m.second.first;
        int y = m.second.second;
        int w = m.first;
        if(dist[y] > dist[x] + w) {
            ciclu_negativ = true;
        }
    }

    if(ciclu_negativ) cout << "Ciclu negativ";
    else {
        for(int i = 2; i < n; i++)
            cout << dist[i] << ' ';
    }

}

int main() {
    int n, m;
    cin >> n >> m;

    for(int i = 0; i < m; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        muchii.push_back({w, {x, y}}); 
    }

    dist.assign(n+1, inf);
    bellman_ford(n, m, 1);
    return 0;
}