#include <bits/stdc++.h>

using namespace std;
typedef unsigned long long ull;
typedef signed long long ll;
typedef unsigned int uint;
typedef unsigned char uchar;
template <typename T>
void printarray(T v[], uint n) {for(uint i = 0; i < n; i ++){cout << v[i] << " ";}cout << endl;}
template <typename T>
void printvector(vector<T> v){for (uint i = 0; i < v.size(); i ++){cout << v[i] << " ";}cout << endl;}
#define dbg(x) cout << #x " = " << x << " | ";
#define dbgnl(x) cout << #x " = " << x << endl;

struct edge_t {
    int finish, cost;
};
const int nmax = 50005;
vector<edge_t> G[nmax];
int n, m;

void read() {
    cin >> n>>m;
    for (int i = 0; i < m; ++i) {
        int s,f,c;
        cin >> s>>f>>c;
        G[s-1].push_back({f-1,c});
    }
}

bitset<nmax> in_queue;
int in_queue_cnt[nmax];
const int INF=2e9;
int best[nmax];
bool negative_cycle = false;

void solve() {
    queue<int> q;
    for (int i = 1; i<n; ++i) {
        best[i] =INF;
    }

    best[0] = 0;
    q.push(0); 
    while (!q.empty() && !negative_cycle) {
        int node = q.front();
        q.pop();
        in_queue[node] = false;
        if (best[node] > INF) continue;

        for (auto edge: G[node]) {
            int new_cost = edge.cost + best[node];
            if (best[edge.finish] > new_cost) {
                best[edge.finish] = new_cost;

                if (!in_queue[edge.finish]) {
                    if (in_queue_cnt[edge.finish] > n) {
                        negative_cycle = true;
                        break;
                    }
                    q.push(edge.finish);
                    in_queue_cnt[edge.finish]++;
                }
            } 
        }  
    }
}

void write() {
    if (negative_cycle) {
        cout << "Ciclu negativ!\n";
    } else
    {
         for (int i = 1; i < n; i++) {
             if (best[i] == INF) cout << "0 ";
             else cout << best[i] << " ";
         }
    }
    cout << "\n";
}

int main() {
    freopen("bellmanford.in", "r", stdin); 
    freopen("bellmanford.in", "w", stdout); 
      
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    read();
    solve();
    write();

    return 0;
}