#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <deque>

using namespace std;

int n, m;
int x, y, c;
int pVerif, newV, cost;
int dist[50002];
int counter[500002];

deque<int> d;

vector<pair<int, int> > graf[50002];

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

void Afis() {
    for (int i = 2; i <= n; i++) {
        cout << dist[i] << ' ';
    }
    cout << "\n";
}

void BellmanFord() {
    int i, j, l;
    d.push_back(1);
    while (!d.empty()) {
        pVerif = d.front();
        d.pop_front();
        for (i = 0, l = graf[pVerif].size(); i < l; i++) {
            newV = graf[pVerif][i].first;
            cost = graf[pVerif][i].second;
            if (dist[newV] > dist[pVerif] + cost) {
                dist[newV] = dist[pVerif] + cost;
                d.push_back(newV);
                counter[newV]++;
            }
            if (counter[newV] == n) {
                fout << "Ciclu negativ!";
                return;
            }
        }
    }
    for (i = 2; i <= n; i++) {
        fout << dist[i] << " ";
    }
}

int main()
{
    int i, j;
    fin >> n >> m;
    for (i = 1; i <= m; i++) {
        fin >> x >> y >> c;
        graf[x].push_back({y, c});
    }

    for (i = 2; i <= n; i++) {
        dist[i] = 999999999;
    }
    dist[1] = 0;
    BellmanFord();
    return 0;
}