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

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

const int Nmax = 50001;
const int INF = INT_MAX;

vector<pair<int, int>> graph[Nmax];
int n, m;

queue <int> q;

int visited[Nmax]; // visited[i] = de cate ori trec prin nodul i
int d[Nmax];
bool inQueue[Nmax];

int bellman_ford(int source) {
    int i, x, y, cost;

    q.push(source); // adaug nodul sursa in coada
    d[source] = 0; // costul nodului sursa este egal cu 0
    visited[source] = 1;
    inQueue[source] = true;

    while (!q.empty()) {
        x = q.front(); // extrag nodul de la inceputul cozii
        q.pop(); // elimin nodul din coada
        inQueue[x] = false;

        // parcurg vecinii y nodului x
        for (i = 0; i < graph[x].size(); i++) {
            y = graph[x][i].first;
            cost = graph[x][i].second;

            if (d[y] > cost + d[x]) {
                d[y] = cost + d[x];
                if (!inQueue[y]) {
                    q.push(y);
                    inQueue[y] = true;
                    visited[y]++;
                }

                if (visited[y] == n) {
                    // trec de n ori prin nodul y -> ciclu negativ
                    return 1;
                }
                
            }
        }
    }

    return 0;
}

int main()
{
    int i, x, y, cost;

    in >> n; // numarul de noduri
    in >> m; // numarul de arce
    for (i = 1; i <= m; i++) {
        in >> x >> y >> cost; // 1 2 1
        graph[x].push_back({y, cost});  
    }

    // initializare cu INF a vectorului d
    for (i = 1; i <= n; i++) {
        d[i] = INF;
    }

    int ciclu = bellman_ford(1);

    if (ciclu == 1) {
        out << "Ciclu negativ!";
        return 0;
    }

    for (i = 2; i <= n; i++) {    
        out << d[i] << " ";
    }

    return 0;
}