#include <algorithm>
#include <bitset>
#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);
}

inline pair<vector<int>, int> bellman_ford2(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());
    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);
    }
     
    return make_pair(D, iterations);
}

inline pair<vector<int>, int> bellman_ford3(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());
    vector<int> changed, next_changed;
    bitset<50001> in_changed;
    
    
    D[0] = 0;
    changed.push_back(0);
    
    for (iterations = 0, ok = true; iterations <= n && ok; ++iterations) {
        ok = false;
        next_changed.clear();
        in_changed.reset();
        
        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;
                
                if (!in_changed[u.first]) {
                    next_changed.push_back(u.first);
                    in_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_ford3(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;
}