#include <iostream>
#include <vector>
#include <fstream>
#include <climits>

using namespace std;

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

struct Edge {
    int src, dest, weight;
};

int n, m;
vector<Edge> edges;

void solve(int startNode) {
    vector<int> distances(n + 1, INT_MAX);
    distances[startNode] = 0;

//    Minimizam edge-urile
    for (int i = 0; i < n; i++) {
        for (auto edge : edges) {
            if (distances[edge.src] != INT_MAX && distances[edge.src] + edge.weight < distances[edge.dest]) {
                distances[edge.dest] = distances[edge.src] + edge.weight;
            }
        }
    }

//    Verificam daca exista cicluri negative - daca rezultatul precedent nu e optim, atunci exista cicluri negative
    for (auto edge : edges) {
        if (distances[edge.src] + edge.weight < distances[edge.dest]) {
            fout << "Ciclu negativ!";
            return;
        }
    }

    for(int i = 2; i <= n; i++) {
        fout << distances[i] << " ";
    }
}

int main() {
//    reading
    fin >> n >> m;
    for(int i = 0; i < m; i++) {
        int src, dest, weight;
        fin >> src >> dest >> weight;
        edges.push_back({src, dest, weight});
    }

    solve(1);
}