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

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

const int NMax = 1e5 + 5;

int N,M;
int dist[NMax];
bool inCoada[NMax];
int nrInCoada[NMax];
// dist[i] = distanta de la nodul 1 la i
// inCoada[i] = true daca nodul i se afla in coada la un moment dat
// nrInCoada[NMax] = numarul de dati in care nodul i a fost introdus in coada =
//                 = lungimea + 1 a unui drum de cost minim ce se termina in i
//                   care a fost gasit la un anumit moment

struct muchie {
    int y,c;
    muchie() {
        muchie(1,0);
    }
    muchie(int a,int b) {
        y = a;
        c = b;
    }
};
vector<muchie> v[NMax];
// v - liste de adiacenta

// shortest path finder algorithm / bellman-ford cu coada

int main() {
    in>>N>>M;
    for (int i=1;i<=M;++i) {
        int x,y,c;
        in>>x>>y>>c;
        muchie e(y,c);
        v[x].push_back(e);
    }

    for (int i=2;i<=N;++i) {
        dist[i] = 1e8;
    }
    dist[1] = 0;

    bool cicluNegativ = false;
    queue<int> Q;
    Q.push(1);
    while (Q.size()) {
        int nod = Q.front();
        Q.pop();
        ++nrInCoada[nod];
        if (nrInCoada[nod]>=N) {
            // daca s-a gasit un drum de N + 1 noduri lungime
            // inseamna ca graful are un ciclu negativ
            cicluNegativ = true;
            break;
        }
        inCoada[nod] = 0;
        vector<muchie>::iterator it;
        for (it = v[nod].begin();it < v[nod].end(); ++it) {
            if (dist[it->y] > dist[nod] + (it->c)) {
                dist[it->y] = dist[nod] + (it->c);
                if (!inCoada[it->y]) {
                    Q.push(it->y);
                }
            }
        }
    }

    if (cicluNegativ) {
        out<<"Ciclu negativ!";
    }
    else {
        for (int i=2;i<=N;++i) {
            out<<dist[i]<<' ';
        }
        return 0;
    }

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