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

pair<vector<int>, int> bellman_ford(const int source, const vector<vector<pair<int, int>>>& G) {
    int iterations = 0, n = G.size();
    bool ok = true;
    vector<int> D(n, numeric_limits<int>::max());
    vector<bool> changed(n, false), next_changed(n);
    
    D[0] = 0;
    changed[0] = true;
    
    for (; 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 (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);
    }
    
    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) // has negative cycle
        fout << "Ciclu negativ!" << endl;
    else
        copy(D.begin()+1, D.end(), ostream_iterator<int>(fout, " ")), fout << endl;
    
    return 0;
}