#include <bits/stdc++.h>
#define int long long

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int n, m, i, nr1, nr2, nr3, aici;
const int maxx = 2147483647;
int test1, test2, test3;

int32_t main()
{
    fin >> n >> m;
    vector <vector <pair<int, int>>> ladj(m);
    queue <int> q;
    vector <int> dist(n+1, maxx);

    for (i = 0; i < m; ++i){
        fin >> nr1 >> nr2 >> nr3;
        ladj[nr1].push_back({nr2, nr3});
    }
    for (i = 1; i <= n; ++i){
        q.push(i);
    }
    dist[1] = 0;
    for (i = 1; i < n && !q.empty(); ++i){
        queue <int> aux;
        //cout << "bombastic\n";
        while (!q.empty()){
            aici = q.front();
            q.pop();
            //cout << "sex";
            for (auto &k : ladj[aici]){
                if (dist[k.first] > dist[aici] + k.second){
                    test1 = dist[aici] + k.second;
                    dist[k.first] = dist[aici] + k.second;
                    aux.push(k.first);
                }
            }
        }
        q = aux;
    }
    while (!q.empty()){
        aici = q.front();
            q.pop();
            for (auto &k : ladj[aici]){
                if (dist[k.first] > dist[aici] + k.second){
                    fout << "Ciclu negativ!\n";
                    return 0;
                }
            }
    }
    for (i = 2; i <= n; ++i){
        fout << dist[i] << ' ';
    }
    fout << '\n';
    return 0;
}