#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;
vector<tuple<int, int, int> > edges, new_edges;
long long dist[Nmax];
vector<pair<int, int>> v[Nmax];


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