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

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

const int NMAX=50001;

vector<tuple<int, int, int>> edges;
int n, m, dist[NMAX];

int main(){
    fin >> n >> m;
    while(m--){
        int a, b, w;
        fin >> a >> b >> w;
        edges.push_back({a, b, w});
    }
    for(int i=1; i<=n; i++) dist[i]=INT_MAX;
    dist[1]=0;
    for(int i=1; i<=n-1; i++){
        for(auto e : edges){
            int a, b, w;
            tie(a, b, w)=e;
            dist[b]=min(dist[b], dist[a]+w);
        }
    }
    int negative_cycle=false;
    for(auto e : edges){
        int a, b, w, aux;
        tie(a, b, w) = e;
        aux = dist[b];
        dist[b]=min(dist[b], dist[a]+w);
        if(dist[b]!=aux){
            negative_cycle=true;
            break;
        }
    }
    if(negative_cycle){
        fout << "Ciclu negativ!";
    }else{
        for(int i=2; i<=n; i++){
            fout << dist[i] << ' ';
        }
    }
}