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

inline pair<vector<int>, int> bellman_ford(const int source, const vector<vector<pair<int, int>>>& G) {
    int iterations, n = G.size();
    bool ok;
    vector<int> D(n, numeric_limits<int>::max());
    set<int> changed, next_changed;
    
    D[0] = 0;
    changed.insert(0);
    
    for (iterations = 0, ok = true; iterations <= n && ok; ++iterations) {
        ok = false;
        next_changed.clear();
        
        for (int v : changed) 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.insert(u.first);
            }
        changed.swap(next_changed);
    }
    
    return make_pair(D, iterations);
}

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));
    }
    
    pair<vector<int>, int> result = bellman_ford(0, G);
    vector<int>& D = result.first;
    int iterations = result.second;
    
    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;
}