#pragma GCC optimize("O3")
#include <bits/stdc++.h>
 
using namespace std;
typedef unsigned long long ll;
typedef pair < int , int > PII;
typedef pair < int , PII >  PIPII;

int n, m, dist[50100], f[50100];

queue < int > Q;
vector < PII > V[50100];
bitset < 50100 > insideH;

inline bool Bellman(int src){
    Q.push(src);
    f[1] = 1;
    
    while (Q.size()){
        int x = Q.front(); Q.pop();
        insideH[x] = 0;
         
        for (auto it : V[x]){
            if (dist[it.first] > dist[x] + it.second){
                ++f[it.first];
                dist[it.first] = dist[x] + it.second;

                if (f[it.first] == n) return 1;

                if (insideH[it.first] == 0){
                    Q.push(it.first);
                    insideH[it.first] = 1;
                }
            }
        }
    }

    return 0;
}

int main(){
    ifstream cin("bellmanford.in");
    ofstream cout("bellmanford.out");
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1, x, y, c; i <= m; i++){
        cin >> x >> y >> c;
        V[x].push_back({y, c});
    }

    for (int i = 2; i <= n; i++) dist[i] = 2e9;

    bool u = Bellman(1);
    if (u) return cout << "Ciclu negativ!", 0;

    for (int i = 2; i <= n; i++)
        cout << (dist[i] == 2e9 ? 0 : dist[i]) << " ";
    return 0;
}