#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

int d[50001], v[50001];
vector <pair<int, int> > mat[50001];
priority_queue <pair <int, int> > q;
pair <int, int> p;
vector <pair<int, int> > :: iterator iv, fv;

int main()
{
    //ifstream in ("date.in");/*
    ifstream in ("bellmanford.in");
    ofstream out ("bellmanford.out");//*/
    int n, m, i, x, y, c;
    in >> n >> m;
    for (i = 0; i < m; ++i) {
        in >> x >> y >> c;
        mat[x].push_back ({y, c});
    }
    q.push({0, 1});
    while (!q.empty()) {
        p = q.top();
        q.pop();
        if (v[i]) {
            if (d[p.second] > -p.first) {
                out << "Ciclu negativ!";
                return 0;
            }
        }
        v[1] = 1;
        d[p.second] = -p.first;
        fv = mat[p.second].end();
        for (iv = mat[p.second].begin(); iv != fv; ++iv) {
            if (d[iv->first] == 0) {
                q.push ({p.first - iv->second, iv->first});
            }
        }
    }

    for (i = 2; i <= n; ++i) {
        out << d[i] << " ";
    }
    return 0;
}