#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;

int N,M,a,b,c;
long long dist[Nmax];
vector<pair<int, int>> v[Nmax];
vector<int> nodes, new_nodes;
bitset<Nmax> changed;


int main()
{
    f>>N>>M;
    for(int i=1;i<=M;i++){
        f>>a>>b>>c;
        v[a].push_back({b, c});
    }
    memset(dist, 127, sizeof(dist));
    dist[1] = 0;
    nodes.push_back(1);
    for(int i=1;i<=N&&nodes.size();i++){
        changed.reset();
        new_nodes.clear();
        for(auto it:nodes)
            for(auto that:v[it])
                if(dist[that.first] > dist[it] + that.second){
                    dist[that.first] = dist[it] + that.second;
                    if(!changed[that.first]){
                        changed[that.first] = true;
                        new_nodes.push_back(that.first);
                    }
                }
        nodes.clear();
        nodes = new_nodes;
    }
    bool negative_cycle_found = false;
        for(auto it:nodes)
            for(auto that:v[it])
                if(dist[that.first] > dist[it] + that.second)
                    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;
}