#include <algorithm>
#include <fstream>
#include <iterator>
#include <limits>
#include <utility>
#include <vector>
using namespace std;

int main() {
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");
    
    int n, m; fin >> n >> m;
    vector<vector<pair<int, int>>> G(n);
    
    for (int u, v, c; m; --m) {
        fin >> u >> v >> c;
        G[u-1].push_back(make_pair(v-1, c));
    }
    
    int iterations;
    bool ok;
    vector<int> D(n, numeric_limits<int>::max());
    vector<bool> changed(n, false), next_changed(n);
    
    D[0] = 0;
    changed[0] = true;
    
    for (iterations = 0, ok = true; iterations <= n && ok; ++iterations) {
        ok = false;
        fill(next_changed.begin(), next_changed.end(), false);
        
        for (int v = 0; v < n; ++v) if (changed[v]) {
            for (const pair<int, int>& u : G[v]) if (D[u.first] > D[v] + u.second) {
                ok = true;
                D[u.first] = D[v] + u.second;
                next_changed[u.first] = true;
            }
        }
        changed.swap(next_changed);
    }
    
    if (iterations == n+1) // has negative cycle
        fout << "Ciclu negativ!" << endl;
    else
        copy(D.begin()+1, D.end(), ostream_iterator<int>(fout, " ")), fout << endl;
    
    return 0;
}