#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>

using namespace std;

#define kNMAX 50011
#define kMAX 1<<30

vector< pair<int, int> > vecini[kNMAX];
queue<int> coada;
int frecventa[kNMAX], cost[kNMAX];
bool inCoada[kNMAX];
int N, M;

int main(){

    fstream in,out;
    in.open("bellmanford.in", ios::in);
    out.open("bellmanford.out", ios::out);

    in >> N >> M;
    for (int i = 1; i <= M; i++){

        int a, b, c;
        in >> a >> b >> c;
        vecini[a].push_back(make_pair(b, c));
    }


    fill(cost, cost + kNMAX, 1<<30 );
    fill(frecventa, frecventa + kNMAX, 0);
    fill(inCoada, inCoada + kNMAX, 0);
    cost[1] = 0;

    coada.push(1);
    inCoada[1] = 1;
    bool ok = false;

    while (!ok && !coada.empty()){

        int x = coada.front();
        coada.pop();
        inCoada[x] = 0;

        for (int i = 0; i < vecini[x].size(); i++){

            int nod, cost1;
            nod = vecini[x][i].first;
            cost1 = vecini[x][i].second;

            if (cost[x] + cost1 < cost[nod]){

                cost[nod] = cost[x] + cost1;
                if (!inCoada[nod]){
                    if (frecventa[nod] > N){
                        ok = true;
                    }else{
                        coada.push(nod);
                        inCoada[nod] = 1;
                        frecventa[nod]++;
                    }

                }
            }
        }

    }

    if (ok)    out << "Ciclu negativ!" << endl;
        else for(int i = 2; i <= N; i++)
            out << cost[i] << " ";

    in.close();
    out.close();
    return 0;
}