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

using namespace std;

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

int N, M;
const int NMAX = 50005;
const int INF = 2000000000;

vector<pair<int, int> > adj[NMAX];
int dist[NMAX], fr[NMAX];
// Min-Heap
priority_queue <pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;

bool existsCycle = false;

void bellmanford(int v) {
    for (int i = 1; i <= N; i++) {
        dist[i] = INF;
        fr[i] = 0; //  resetam si frecventa
    }

    dist[v] = 0;
    pq.push(make_pair(0, v));

    while (!pq.empty()) {
        pair<int,int> k = pq.top();
        pq.pop();

        int nod_curent = k.second;
        int dist_curenta = k.first;

        // Aceasta verificare evita procesarea intrarilor vechi din heap (optimizare)
        if (dist_curenta > dist[nod_curent]) continue;

        fr[nod_curent]++;
        if (fr[nod_curent] > N) { // > N sau == N e ok pentru detectie
            existsCycle = true;
            return;
        }

        for (auto x : adj[nod_curent]) {
            int vecin = x.first;
            int cost = x.second;

            if (dist[vecin] > dist[nod_curent] + cost) {
                // actualizez distanta
                dist[vecin] = dist[nod_curent] + cost;
                pq.push(make_pair(dist[vecin], vecin));
            }
        }
    }
}

int main() {
    fin >> N >> M;
    int x, y, c;
    for (int i = 0; i < M; i++) {
        fin >> x >> y >> c;
        adj[x].push_back(make_pair(y, c));
    }

    bellmanford(1);

    if (existsCycle) {
        fout << "Ciclu negativ!";
    }
    else {
        for (int i = 2; i <= N; i++) {
            if (dist[i] == INF) fout << "0 "; // De obicei se afiseaza 0 daca nu e drum
            else fout << dist[i] << " ";
        }
    }
    return 0;
}