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

constexpr int maxn = 50000;

int n, m, min_dist[maxn] = {};
vector<int> random_ordering;
vector<tuple<int, int, int>> up_graf, down_graf;

bool done_something;
void relax_edge(const int x, const int y, const int len){
    if(min_dist[x] + len < min_dist[y]){
        min_dist[y] = min_dist[x] + len;
        done_something = true; } }

bool do_bellman_iteration(){
    done_something = false;
    for(const auto x : up_graf)
        relax_edge(get<0>(x), get<1>(x), get<2>(x));
    for(const auto x : down_graf)
        relax_edge(get<0>(x), get<1>(x), get<2>(x));
    return done_something; }

bool do_bellman(){
    fill(begin(min_dist), end(min_dist), 1e9);
    min_dist[0] = 0;
    for(int i = 0; i <= n/2 + 5; ++i)
        if(!do_bellman_iteration())
            return true;
    return false; }

int main(){
    ifstream f("bellmanford.in");
    ofstream g("bellmanford.out");
    f >> n >> m;

    random_ordering.resize(n);
    iota(begin(random_ordering), end(random_ordering), 0);
    srand(time(nullptr));
    random_shuffle(begin(random_ordering), end(random_ordering));

    for(int i = 0, x, y, t; i < m; ++i){
        f >> x >> y >> t;
        --x, --y;
        (random_ordering[x] < random_ordering[y] ? up_graf : down_graf).emplace_back(x, y, t); }

    sort(begin(up_graf), end(up_graf), [](const tuple<int, int, int>& a, const tuple<int, int, int>& b){
        return random_ordering[get<0>(a)] < random_ordering[get<0>(b)]; });
    sort(begin(down_graf), end(down_graf), [](const tuple<int, int, int>& a, const tuple<int, int, int>& b){
        return random_ordering[get<0>(a)] > random_ordering[get<0>(b)]; });

    if(!do_bellman()) g << "Ciclu negativ!" << endl;
    else for(int i = 1; i < n; ++i) g << min_dist[i] << ' ';
    return 0; }