#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]) {continue;}
        v[p.second] = 1;
        d[p.second] = -p.first;
        fv = mat[p.second].end();
        for (iv = mat[p.second].begin(); iv != fv; ++iv) {
            if (v[iv->first] != 1) {
                q.push ({p.first - iv->second, iv->first});
            }
            else {
                if (-p.first + iv->second < d[iv->first]) {
                    out << "Ciclu negativ!";
                    return 0;
                }
            }
        }
    }

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