#include <iostream>
#include <vector>
#include <queue> 

using namespace std;

int main(){
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);

    int n,m;
    cin >> n >> m;

    vector<vector<pair<int,int>>> adj(n+1);

    for(int i = 0;i < m; ++i){
        int x, y, c;
        cin >> x >> y >> c;
        adj[x].push_back({y,c});
    }
    
    vector<long long> dist(n+1,__LONG_LONG_MAX__);
    vector<int> cnt(n+1,0);
    vector<bool> inCoada(n+1,false);

    queue<int> q;
    dist[1] = 0;
    q.push(1);
    inCoada[1] = true;
    cnt[1]++;

    bool CicluNegativ = false;

    while(!q.empty() && !CicluNegativ){
        int x = q.front();
        q.pop();
        inCoada[x] = false;

        for(int i = 0;i < adj[x].size(); ++i){
            int y = adj[x][i].first;
            int c = adj[x][i].second;

            if(dist[x] != __LONG_LONG_MAX__ && dist[x] + c < dist[y]){
                dist[y] = dist[x] + c;

                if(!inCoada[y]){
                    q.push(y);
                    cnt[y]++;
                    inCoada[y] = true;

                    if(cnt[y] > n){
                        CicluNegativ = true;
                        break;
                    }
                }
            }
        }
    }

    if(CicluNegativ)
        cout << "Ciclu negativ!";
    else{
        for(int i = 2;i <= n; ++i)
            cout << dist[i] << " ";
    }

    return 0;
}