#include <bits/stdc++.h>

using namespace std;

int dist[50001];
bool inq[50001];
int cmin[50001];
vector<pair<int, int>> adj[50001];

int main(){
    
    ifstream cin("bellmanford.in");
    ofstream cout("bellmanford.out");
    
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({b, c});
    }
    queue<int> q;
    q.push(1);
    inq[1] = 1;
    cmin[1] = 0;
    for(int i = 2; i <= n; i++) cmin[i] = 1e18;
    bool cycle = 0;
    while(!q.empty()){
        int node = q.front();
        q.pop();
        inq[node] = 0;
        for(auto [a, b] : adj[node]){
            if(cmin[node] + b < cmin[a]){
                cmin[a] = cmin[node] + b;
                dist[a] = dist[node] + 1;
                if(dist[a] > n){
                    cycle = 1;
                    break;
                }
                if(!inq[a]){
                    inq[a] = 1;
                    q.push(a);
                }
            }
        }
    }
    if(cycle){
        cout << "Ciclu negativ!";
        return 0;
    }
    for(int i = 2; i <= n; i++){
        cout << cmin[i] << " ";
    }
    return 0;
}