#include <iostream>
#include <fstream>
#include <bits/stdc++.h>

using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

const int Nmax =  50010;
const int Mmax = 250010;
const long long Valmax = 10000000000;
typedef pair<long long, int> value_pair;

class Compare{
public:
    bool operator()(value_pair a, value_pair b){
        return a.first > b.first;
    }
};

int N,M,a[Mmax],b[Mmax],c[Mmax];
vector<pair<int,int> > v[Nmax];
long long dist[Nmax];
priority_queue<value_pair, vector<value_pair>, Compare> q;


int main()
{
    f>>N>>M;
    for(int i=1;i<=M;i++){
        f>>a[i]>>b[i]>>c[i];
        v[a[i]].push_back({b[i], c[i]});
    }
    memset(dist, 127, sizeof(dist));
    dist[1] = 0;
    bool keep_going = true;
    for(int i=1;i<=N&&keep_going;i++){
        keep_going = false;
        for(int j=1;j<=M;j++)
            if(dist[b[j]] > dist[a[j]] + c[j]){
                dist[b[j]] = dist[a[j]] + c[j];
                keep_going = true;
            }
    }
    bool negative_cycle_found = false;
    for(int j=1;j<=M;j++)
        if(dist[b[j]] > dist[a[j]] + c[j])
            negative_cycle_found = true;

    if(negative_cycle_found)
        g<<"Ciclu negativ!";
    else{
        for(int i=2;i<=N;i++)
            if(dist[i] > Valmax)
                g<<"0 ";
            else
                g<<dist[i]<<' ';
    }
    return 0;
}