#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<pair<int, int>>> lv;
    vector<int> nrVizitare(n ,0);
    int ok = 1;

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

    vector<int> dist(n, 1e9);
    queue<int> coada;
    coada.push(0);

    dist[0] = 0;

    while(coada.empty() == false){
        int nod = coada.front();
        coada.pop();
        if (++nrVizitare[nod] == n){
            g << "Ciclu negativ!";   
            ok = 0;
            break;
        }
        else{
            for (int i = 0; i < lv[nod].size(); i++){
                int nodVecin = lv[nod][i].first;
                int cost = lv[nod][i].second;

                if (dist[nod] + cost < dist[nodVecin]){
                    dist[nodVecin] = cost + dist[nod];
                    coada.push(nodVecin);
                }
            }            
        }
    }

    if (ok == 1){
        for (int i = 1; i < n; i++){
            g << dist[i] << " ";
        }
    } 

    return 0;
}