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

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

vector<int> BF(int src, vector<vector<int> > &edges, int n, int m, bool &neg) {
    vector<int> dist(n + 1, INT_MAX);
    dist[src] = 0;

    // Relax all edges n-1 times
    for (int k = 1; k <= n - 1; k++) {
        for (int i = 1; i <= m; i++) {
            int u = edges[i][0];
            int v = edges[i][1];
            int c = edges[i][2];

            if (dist[u] != INT_MAX && dist[v] > dist[u] + c) {
                dist[v] = dist[u] + c;
            }
        }
    }

    // One more pass to detect a negative cycle
    neg = false;
    for (int i = 1; i <= m; i++) {
        int u = edges[i][0];
        int v = edges[i][1];
        int c = edges[i][2];

        if (dist[u] != INT_MAX && dist[v] > dist[u] + c) {
            neg = true;
            break;
        }
    }

    return dist;
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int> > edges(m + 1, vector<int>(3));
    for (int i = 1; i <= m; i++) {
        cin >> edges[i][0] >> edges[i][1] >> edges[i][2];
    }

    bool neg = false;
    vector<int> dist = BF(1, edges, n, m, neg);

    if (neg) {
        cout << "Ciclu negativ!";
    } else {
        for (int i = 2; i <= n; i++) {
            if(dist[i]!=INT_MAX)
                cout << dist[i] << ' ';
        }
    }

    return 0;
}