#include <bits/stdc++.h>

using namespace std;

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

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

void clear(queue <int> & q){
    queue <int> empty;
    swap(q, empty);
}


int32_t main()
{
    fin >> n >> m;
    vector <vector <pair<int, int>>> ladj(m);
    queue <int> q;
    vector <long long> dist(n+1, maxx);
    queue <int> aux;
    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){
        clear(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){
                    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;
}