#include <bits/stdc++.h>
using namespace std;
typedef pair <int,int> pii;

#define fi first
#define se second
const int N = 50010;
int n, m, d[N], cnt[N];
queue <int> Q;
vector <pii> v[N];
bool u[N];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    ifstream cin ("bellmanford.in");
    ofstream cout ("bellmanford.out");
    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++) d[i] = (1<<30);
    Q.push(1);
    while (!Q.empty()){
        int nod = Q.front();
        Q.pop();
        u[nod] = 0;
        if (d[nod] == (1<<30)) continue;
        for (auto it: v[nod]){
            if (d[nod] + it.se < d[it.fi]){
                d[it.fi] = d[nod] + it.se;
                if (u[it.fi]) continue;
                if (cnt[it.fi] > n) return cout << "Ciclu negativ!\n", 0;
                Q.push(it.fi);
                u[it.fi] = 1;
                cnt[it.fi]++;
            }
        }
    }
    for (int i=2; i<=n; i++) cout << d[i] << " ";
    return 0;
}