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

inline pair<vector<int>, bool> bellman_ford(const int source, const vector<vector<pair<int, int>>>& G) {
    vector<int> D(G.size(), numeric_limits<int>::max());
    queue<int> Q;
    vector<bool> inQ(G.size(), false);
    vector<int> times_inQ(G.size(), 0);
    
    D[source] = 0;
    Q.push(source);
    inQ[source] = true;
    times_inQ[source]++;
    
    bool has_negative_cycle = false;
    while (!Q.empty() && !has_negative_cycle) {
        int u = Q.front(); Q.pop();
        inQ[u] = false;
        
        for (const pair<int, int>& v : G[u])
            if (D[v.first] > D[u] + v.second) {
                D[v.first] = D[u] + v.second;
                
                if (!inQ[v.first]) {
                    Q.push(v.first);
                    inQ[v.first] = true;
                    times_inQ[v.first]++;
                    
                    if (times_inQ[v.first] >= G.size()) {
                        has_negative_cycle = true;
                        break;    
                    }
                }
            }
    }
    
    return make_pair(D, has_negative_cycle);
}

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>, bool> result = bellman_ford(0, G);
    vector<int>& D = result.first;
    bool has_negative_cycle = result.second;
    
    if (has_negative_cycle)
        fout << "Ciclu negativ!" << endl;
    else
        copy(D.begin()+1, D.end(), ostream_iterator<int>(fout, " ")), fout << endl;
    
    return 0;
}