#include <bits/stdc++.h>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int n, m, cnt[50001], d[50001];
bool v[50001];
vector<pair<int, int>> a[50001];

bool bf(int u){
    for(int i = 1; i<=n; i++)
        d[i] = INT_MAX;

    queue<int> q;
    d[u] = 0;
    v[u] = 1;
    q.push(u);
    while(!q.empty()){
        int s = q.front();
        q.pop();
        v[s] = 0;
        for(auto it : a[s]){
            int nv = it.first;
            int nc = it.second;
            if(d[nv] > d[s] + nc){
                d[nv] = d[s] + nc;
                if(!v[nv]){
                    v[nv] = 1;
                    q.push(nv);
                    cnt[nv]++;
                    if(cnt[nv] > n)
                        return false;
                }
            }
        }
    }
    return true;
}

int main(){
    fin >> n >> m;

    for(int i = 1; i<=m; i++){
        int x, y, l;
        fin >> x >> y >> l;
        a[x].push_back(make_pair(y, l));
    }

    if(bf(1)){
        for(int i = 2; i<=n; i++)
            fout << d[i] << ' ';
    }
    else
        fout << "Ciclu negativ!";

    return 0;
}