#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

struct Nod {
    int nod, cost;
};

struct Entry {
    int nod, dist;
    bool operator<(const Entry& other) const {
        return dist > other.dist;
    }
};

int n, m;
vector<Nod> list[50001];
int d[50001];
int vizitat[50001];
int INF = 0x3f3f3f3f;
bool ok = true;


void bf() {
    d[1] = 0;
    priority_queue<Entry> q;
    q.push({1, 0});

    while (!q.empty()) {
        auto elem = q.top();
        q.pop();
        vizitat[elem.nod]++;
        if (vizitat[elem.nod] > n) {
            ok = false;
            return;
        }

        for (int i = 0; i < list[elem.nod].size(); i++) {
            auto vecin = list[elem.nod][i];
            if ( d[elem.nod] + vecin.cost < d[vecin.nod]) {
                d[vecin.nod] = d[elem.nod] + vecin.cost;
                q.push({ vecin.nod, d[vecin.nod] });
            }
        }

    }
}

int main()
{
    ifstream cin("bellmanford.in");
    ofstream cout("bellmanford.in");
    memset(d, INF, sizeof(d));

    cin >> n >> m; 
    int a, b, c;
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b >> c;
        list[a].push_back({ b, c });
    }

    bf();

    if (ok) {
        for (int i = 2; i <= n; i++) {
            cout << d[i] << " ";
        }
    }
    else {
        cout << "Ciclu negativ!";
    }

}