#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
using namespace std;

using ll = long long;
using ull = unsigned long long;
using point = complex<int>;
using pii = pair<int , int>;

template <typename T>
using pair2 = pair<T , T>;
template <typename T>
using min_queue = priority_queue< T , vector<T> , greater<T>>;

const int inf = int(1e9);
const ll inf_64 = ll(1e18);
const long double eps = 1e-9;
const int dx[4] = {1 , 0 , -1 , 0};
const int dy[4] = {0 , 1 , 0 , -1};

#define FOR(i , n) for(int (i) = 0 ; (i) < (n) ; (i)++)
#define apare cout << "apare\n";
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sort_up(x) sort(all(x))
#define sort_down(x) sort(rall(x))
#define fi first
#define se second
#define re real()
#define im imag()
#define endl "\n"

//#define _DEBUG
#define _FILES

//// subprograms for the problem

vector<tuple<int , int , int>> edges;

void test_case(){
    int n , m;
    cin >> n >> m;
    vector<int>d(n+1 , +inf);
    for(int i = 0 ; i < m ; i++){
        int a , b , w;
        cin >> a >> b >> w;
        edges.push_back(make_tuple(a, b , w));
    }
    d[1] = 0;
    for(int i = 0 ; i < n - 1 ; i++){
        for(auto edge : edges){
            if(d[get<0>(edge)] + get<2>(edge) < d[get<1>(edge)]){
                d[get<1>(edge)] = d[get<0>(edge)] + get<2>(edge);
            }
        }
    }
bool negative_cycle = false;
    for(int i = 0 ; i < n - 1 ; i++){
        for(auto edge : edges){
            if(d[get<0>(edge)] + get<2>(edge) < d[get<1>(edge)]){
                negative_cycle = true;
            }
        }
        if(negative_cycle)break;
    }
    if(negative_cycle){
        cout << "Ciclu negativ!" << endl;
    }
    else {
        for (int i = 2; i <= n; i++) {
            cout << d[i] << " ";
        }
    }
}


signed main() {
#ifdef _DEBUG
    freopen("data.in" , "r" , stdin);
    freopen("data.out" , "w" , stdout);
    int t = clock();
#endif
#ifdef _FILES
    freopen("bellmanford.in" , "r" , stdin);
    freopen("bellmanford.out" , "w" , stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(15);
///code for the problem
///===============================================================
    test_case();
///===============================================================
///debugging
#ifdef _DEBUG
    cerr << "Time = " << clock() - t << "ms" << endl;
    std::time_t current_time = std::time(0);
    std::tm* now = std::localtime(&current_time);
    cerr << "Date = " << (now -> tm_year + 1900) << " : " << (now -> tm_mon + 1) << " : " << (now -> tm_mday) << endl;
    cerr << "Hour = " << (now -> tm_hour) << ":" << (now -> tm_min) << ":" << (now -> tm_sec)<< endl;
#endif
    return 0x0;
}