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

const int NMAX = 50005;
const int INF = 1000000000; // puteam pune NMAX * cost_max = 50.000 * 1000

struct Edge {
    int neighbor;
    int cost;
};

vector<Edge> graph[NMAX];

int dist[NMAX]; // dist[i] := distanta de la 1 la i
queue<int> que; // coada pentru algoritm
bool inQue[NMAX]; // inQue[i] := true daca i se afla acum in coada
int numUpdates[NMAX]; // numUpdates[i] := de cate ori am updatat nodul i


int main() {
     ifstream cin("bellmanford.in");
     ofstream cout("bellmanford.out");

    int N, M;
    cin >> N >> M;
    for (int i = 0; i < M; ++i) {
        int x, y, cost;
        cin >> x >> y >> cost;
        Edge e;
        e.neighbor = y;
        e.cost = cost;
        graph[x].push_back(e);
    }

    // coada: initial adaugam nodul de start
    // cat timp avem elemente in coada:
    //   extragem elementul curent
    //   parcurgem toti vecinii
    //     daca obtinem pentru un vecin un cost mai bun, il adaugam la coada (daca nu se afla deja in coada)
    //     mai retinem de cate ori a fost updatat un nod (daca a fost uipdatat de mai mult de N ori, avem ciclu de cost negativ)


    // Initializari
    dist[1] = 0;
    for (int i = 2; i <= N; ++i)
        dist[i] = INF;
    que.push(1);  // adaugam nodul sursa la coada
    inQue[1] = true; // 1 se afla in coada

    while (!que.empty()) {
        int node = que.front();
        que.pop(); // am scos primul element din coada
        inQue[node] = false;

        for (Edge& e : graph[node]) {  // folosim referinta pentru a nu copia fiecare muchie in parte
            if (dist[e.neighbor] > dist[node] + e.cost) {
                dist[e.neighbor] = dist[node] + e.cost;
                if (!inQue[e.neighbor]) {
                    que.push(e.neighbor);
                    inQue[e.neighbor] = true;
                }
                numUpdates[e.neighbor]++;
                if (numUpdates[e.neighbor] > N) {
                    cout << "Ciclu negativ!\n";
                    return 0;
                }
            }
        }
    }

    for (int i = 2; i <= N; ++i)
        cout << dist[i] << " ";
    cout << "\n";

    return 0;
}