#include <fstream>
#include <vector>
#include <climits>

struct Csucs{
    int honnan, hova, ertek;
};

int main(){
    std::ifstream be("bellmanford.in");
    std::ofstream ki("bellmanford.out");
    int n, m;
    be >> n >> m;
    std::vector<Csucs> csucsok;
    for(int i = 0; i < m; i++){
        int honnan, hova, ertek;
        be >> honnan >> hova >> ertek;
        honnan--; hova--;
        csucsok.push_back({honnan, hova, ertek});
    }
    std::vector<int> tavolsag(n, INT_MAX);
    tavolsag[0] = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            if(tavolsag[csucsok[j].honnan] + csucsok[j].ertek < tavolsag[csucsok[j].hova] && tavolsag[csucsok[j].honnan] != INT_MAX)
                tavolsag[csucsok[j].hova] = tavolsag[csucsok[j].honnan] + csucsok[j].ertek;

    bool megvaltozott = 0;
    for(int j = 0; j < m && !megvaltozott; j++)
        if(tavolsag[csucsok[j].honnan] + csucsok[j].ertek < tavolsag[csucsok[j].hova] && tavolsag[csucsok[j].honnan] != INT_MAX)
            megvaltozott = 1;
    if(megvaltozott)
        ki << "Ciclu negativ!";
    else
        for(int i = 1; i < n; i++)
            ki << tavolsag[i] << ' ';
    be.close();
    ki.close();
    return 69;
}