#include <bitset>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

const int MAX_N = 50001;
const int INF = 1000000000;

struct arc {
    int extremitate;
    int cost;
};

vector<arc> arce[MAX_N];
queue<int> q;
bitset<MAX_N> in_coada;
vector<int> dist(MAX_N, INF);
int ap_in_coada[MAX_N], x, y, c, n, m, i;
arc a;
bool ciclu_negativ;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int main() {
    fin >> n >> m;
    for (i = 1; i <= m; i++) {
        fin >> x >> a.extremitate >> a.cost;
        arce[x].push_back(a);
    }
    dist[1] = 0, q.push(1), in_coada[1] = true;
    while (not q.empty() and not ciclu_negativ) {
        x = q.front();
        q.pop();
        in_coada[x] = false;
        for (auto arc : arce[x])                              // pentru toate arcele care pleaca din x
            if (dist[arc.extremitate] > dist[x] + arc.cost) { // Distanta pana la arc.extremitate poate fi imbunatatita.
                dist[arc.extremitate] = dist[x] + arc.cost;   // Actualizam distanta cu valoarea mai buna.
                if (not in_coada[arc.extremitate])
                    if (ap_in_coada[arc.extremitate] == n)
                        ciclu_negativ = true;
                    else {
                        q.push(arc.extremitate); // Ar putea aduce imbunatatiri mai tarziu.
                        in_coada[arc.extremitate] = true;
                        ap_in_coada[arc.extremitate]++;
                    }
            }
    }
    if (not ciclu_negativ) {
        for (i = 2; i <= n; i++)
            fout << dist[i] << " ";
    }
    else
        fout << "Ciclu negativ!\n";
    return 0;
}

/*
1->2
     t  x  y  z  s
     6 oo  7 oo  0
t,x: 6 11  7 oo  0
t,z: 6 11  7  2  0
y,x: 6  4  7  2  0
------------------
2->3
     t  x  y  z  s     
     6  4  7  2  0
x,t: 2  4  7  2  0
------------------
3->4
     u  v  x  y  z
     t  x  y  z  s
     2  4  7  2  0
t,z: 2  4  7 -2  0
*/