#include <bits/stdc++.h>
using namespace std;

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

    int n, m, nod1, nod2, cost;

    f >> n >> m;
    vector<vector<int>> muchii;

    for (int i = 0; i < m; i++){
        vector<int> a;
        muchii.push_back(a);
    }
    
    for (int i = 0; i < m; i++){
        f >> nod1;
        f >> nod2;
        f >> cost;
        muchii[i].push_back(nod1 - 1);
        muchii[i].push_back(nod2 - 1);
        muchii[i].push_back(cost);
    }

    vector<int> dist(n, 1e9);
    vector<int> vizitat(n, false);

    dist[0] = 0;

    for (int i = 0; i < n; i ++){
        for (int j = 0; j < m; j++) {
            int sursa = muchii[j][0];
            int destinatie = muchii[j][1];
            cost = muchii[j][2];

            if (dist[sursa] + cost < dist[destinatie])
                dist[destinatie] = cost + dist[sursa];
        }
    }

    int ok = 1;

    for (int j = 0; j < m; j++) {
        int sursa = muchii[j][0];
        int destinatie = muchii[j][1];
        cost = muchii[j][2];

        if (dist[sursa] + cost < dist[destinatie]){
            g << "Ciclu negativ!";   
            ok = 0;
        }
    }
    if (ok == 1){
        for (int i = 1; i < n; i++){
            g << dist[i] << " ";
        }
    }
    
    return 0;
}