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

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

const int INF = 0x3f3f3f3f;

struct arc
{
    int y, c;/* data */
};

#define QI queue<int>
#define VB vector<bool>
#define VI vector<int>
#define VA vector<arc>
#define VVA vector<VA>
#define pb push_back

int n, m;
VI costMin;
VVA lisAd;
bool cicluNeg = false;

void BellmanFord(int start) {
    costMin[start] = 0;
    QI noduri;
    noduri.push(start);
    VI nrVizitari(n + 1, 0);
    VB folosit(n + 1, false);
    folosit[start] = true;
    while (!noduri.empty() && !cicluNeg) {
        int nodC = noduri.front();
        noduri.pop();
        ++nrVizitari[nodC];
        folosit[nodC] = false;
        if (nrVizitari[nodC] > n) {
                cicluNeg = true;
                break;
        }
        for (auto vecin : lisAd[nodC]) {
            int cost = costMin[nodC] + vecin.c;
            if (costMin[vecin.y] > cost) {
                costMin[vecin.y] = cost;
                if (!folosit[vecin.y]) {
                    folosit[vecin.y] = true;
                    noduri.push(vecin.y);   
                }
            }
        }
    }
}

void printCosturi() {
    for (int nod = 2; nod <= n; ++nod) {
        fout << costMin[nod] << ' ';
    }
}


int main() {
    fin >> n >> m;
    costMin = VI(n + 1, INF);
    lisAd = VVA(n + 1);
    for (int i = 0; i < m; ++i) {
        arc edge;
        int x;
        fin >> x >> edge.y >> edge.c;
        lisAd[x].pb(edge);
    }

    BellmanFord(1);
    if (cicluNeg) {
        fout << "Ciclu negativ!";
    } else {
        printCosturi(); 
    }
}

/*
avem un nod, vrem sa vedem daca imbunatatim costurile vecinilor sai
Daca da, ii bagam in coada.
*/

/*
. Astfel, se poate ţine o listă de noduri, la fiecare pas scoţând 
un element din aceasta. Se va încerca îmbunătăţirea costului nodurilor vecine, 
introducându-le în listă în cazul scăderii costului, dacă nu apar deja. 
Această listă se poate implementa printr-un heap, selectând la fiecare pas nodul
 de cost minim, soluţia obţinând 100 de puncte, sau printr-o coadă, soluţia obţinând, de asemenea, 100 de puncte. Deşi au complexităţi teoretice de O(N*M*log2N), respectiv O(N*M), cele două soluţii se comportă mult mai bine în practică
*/