#include <iostream>
#include <fstream>
#include <queue>
#include <limits.h>
#define NLIM 50001
#define MLIM 250001

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

int n, m, D[NLIM], viz[NLIM], inCoada[NLIM];
queue<int> Coada;
vector< pair<int, int> > Muchii[MLIM];

bool BellmanFord(int start) {
    D[start] = 0;
    Coada.push(start);
    inCoada[start] = 1;

    while(!Coada.empty()) {
        int nod = Coada.front();
        if(viz[nod] >= n)
            return 0;
        Coada.pop();
        inCoada[nod] = 0;

        for(int i=0; i<Muchii[nod].size(); i++) {
            int v = Muchii[nod][i].first;
            int c = Muchii[nod][i].second;
            if(D[nod]+c < D[v]) {
                D[v] = D[nod]+c;
                if(!inCoada[v]) {
                    Coada.push(v);
                    viz[v]++;
                    inCoada[v] = 1;
                }
            }
        }
    }
    return 1;
}

void citire() {
    f >> n >> m;
    for(int i=1; i<=n; i++) {
        D[i] = INT_MAX;
        viz[i] = 0;
        inCoada[i] = 0;
    }
    for(int i=1; i<=m; i++) {
        int s, d, c;
        f >> s >> d >> c;
        Muchii[s].push_back(make_pair(d, c));
    }
}
void afisare(bool state) {
    if(!state)
        g << "Ciclu negativ!";
    else for (int i = 2; i <= n; ++i)
            if(D[i] != INT_MAX)
                g << D[i] << ' ';
    g << '\n';
}
int main() {
    citire();
    afisare(BellmanFord(1));
    return 0;
}