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

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

const int NMAX = 250005;
int n, m, dist[NMAX];
bool ciclu_negativ;
struct Muchie
{
    int x, y, c;
};

vector < Muchie > muchii;

void read() {
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b, cost;
        fin >> a >> b >> cost;
        dist[a] = NMAX + 5;
        dist[b] = NMAX + 5;
        Muchie muc;
        muc.x = a;
        muc.y = b;
        muc.c = cost;
        muchii.push_back(muc);
    }
}

void bellman_ford(int s) {
    ciclu_negativ = false;
    dist[s] = 0;
    for (int i = 1; i <= n - 1; i++) {
        for (int j = 0; j < m; j++) {
            if (dist[muchii[j].y] > dist[muchii[j].x] + muchii[j].c)
                dist[muchii[j].y] = dist[muchii[j].x] + muchii[j].c;
        }
    }
    for (int j = 0; j < m && !ciclu_negativ; j++) {
        if (dist[muchii[j].y] > dist[muchii[j].x] + muchii[j].c) {
            ciclu_negativ = true;
        }
    }
    if (ciclu_negativ)
        fout << "Ciclu negativ";
    else
        for (int i = 2; i <= n; i++)
            fout << dist[i] << " ";
}

int main()
{
    read();
    bellman_ford(1);
}