#include<iostream>
#include <stdio.h>
#include <vector> 
#include <map>
#include <string.h>

using namespace std;

#define INF 1000000001

struct Neighbor {
    int v;
    int cost;

    Neighbor(int x, int c) : v(x), cost(c) {
    }
};

void computeSSSD(int distance[], int N, map<int, vector<Neighbor> >& graph) {

    for (int i = 0; i < N - 1; i++) {
        map<int, vector<Neighbor> >::iterator git = graph.begin();
        for (; git != graph.end(); ++git) {
            int u = git->first;
            vector<Neighbor> neigh = git->second;
            for (int j = 0; j < neigh.size(); j++) {
                int v = neigh[j].v;
                if (distance[u] + neigh[j].cost < distance[v]) {
                    distance[v] = distance[u] + neigh[j].cost;
                }
            }
        }
    }
}

bool containsCycle(int distance[], int N, map<int, vector<Neighbor> >& graph) {
    map<int, vector<Neighbor> >::iterator git = graph.begin();
    for (; git != graph.end(); ++git) {
        int u = git->first;
        vector<Neighbor> neigh = git->second;
        for (int j = 0; j < neigh.size(); j++) {
            int v = neigh[j].v;
            if (distance[v] > distance[u] + neigh[j].cost) {
                return true;
            }
        }
    }

    return false;
}

int main() {
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);

    int N, M;
    cin >> N >> M;
    map<int, vector<Neighbor> > graph;
    for (int i = 0; i < M; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        graph[u].push_back(Neighbor(v, c));
    }
    int distance[N + 1];
    for (int i = 1; i <= N; i++) {
        distance[i] = INF;
    }
    distance[1] = 0;
    computeSSSD(distance, N, graph);
    bool cycle = containsCycle(distance, N, graph);
    if (cycle) {
        cout << "Ciclu negativ!" << endl;
    } else {
        for (int i = 2; i <= N; i++) {
            cout << distance[i];
            if (i <= N - 1) {
                cout << " ";
            }
        }
        cout << endl;
    }
    fclose(stdout);
    return 0;

}