#include <bits/stdc++.h>
using namespace std;

int n, m, d[50010];
struct edge{
    int a, b, c;
} M[250010];
vector <int> v[50010];
set <pair<int,int> > S;
bool u[50010];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ifstream cin ("bellmanford.in");
    ofstream cout ("bellmanford.out");
    cin >> n >> m;
    for (int i=1; i<=m; i++){
        cin >> M[i].a >> M[i].b >> M[i].c;
        v[M[i].a].push_back(i);
    }
    for(int i=2; i<=n; i++) d[i] = (1<<30);
    S.insert({0, 1});
    for (long long pas = 0; pas <= 1LL*n*m/2 && S.size(); pas++){
        int nod = S.begin()->second;
        S.erase(S.begin());
        //u[nod] = 0;
        for (auto it: v[nod]){
            if (d[nod] + M[it].c < d[M[it].b]){
                d[M[it].b] = d[nod] + M[it].c;
                /*if (!u[M[it].b]){
                    u[M[it].b] = 1;
                    S.insert({d[M[it].b], M[it].b});
                }*/
                S.insert({d[M[it].b], M[it].b});
            }
        }
    }
    for (int i=1; i<=m; i++)
        if (d[M[i].a] + M[i].c < d[M[i].b]) return cout << "Ciclu negativ!", 0;
    for (int i=2; i<=n; i++) cout << d[i] << " ";
    return 0;
}