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

ifstream f ("bellmanford.in");
ofstream g ("bellmanford.out");

struct muchie {
    int nod, cost;
    muchie (int nod, int cost) {
        this->nod = nod;
        this->cost = cost;
    }
};

const int nmax = 50000;
const int inf = 0x3f3f3f3f;

int n;
queue <int> q;
vector <muchie> v[nmax + 1];
int cost[nmax + 1], a[nmax + 1];
bool viz[nmax + 1];

void citeste () {
    int m;
    f >> n >> m;
    int a, b, c;
    for (int i = 1; i <= m; i++) {
        f >> a >> b >> c;
        muchie M = muchie (b,c);
        v[a].push_back (M);
    }
}

int answer () {
    q.push (1);
    for (int i = 2; i <= n; i++) cost[i] = inf;
    int x, y, c;
    while (!q.empty ()) {
        x = q.front ();
        viz[x] = false;
        q.pop ();
        for (int i = 0; i < v[x].size (); i++) {
            y = v[x][i].nod;
            c = v[x][i].cost;
            if (cost[y] > cost[x] + c) {
                cost[y] = cost[x] + c;
                if (!viz[y]) {

                    if (a[y] > n) return 1;
                    a[y]++;
                    q.push (y);
                    viz[y] = true;
                }

            }

        }
    }
    return 0;

}


int main () {
    citeste ();
    if (answer ()) g << "Ciclu negativ!";
    else
        for (int i = 2; i <= n; i++) g << cost[i] << ' ';
    g << '\n';
    return 0;
}