#include <bits/stdc++.h>

using namespace std;

#define SIZE(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()

typedef long long int64; typedef unsigned long long uint64;
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;

const int NMAX = 50005;

vector<pair<int, int>> g[NMAX];
int dist[NMAX];
int N, M;

bool bellmanFord(int source) {
    dist[source] = 0;
    for (int k = 0; k < N - 1; k++) {
        for (int u = 1; u <= N; u++) {
            for (pair<int, int>& e : g[u]) {
                int v = e.second, w = e.first;
                if (dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                }
            }
        }
    }
    for (int u = 1; u <= N; u++) {
        for (pair<int, int>& e : g[u]) {
            int v = e.second, w = e.first;
            if (dist[v] > dist[u] + w) return false;
        }
    }
    return true;
}

int main() {
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int x, y, w; cin >> x >> y >> w;
        g[x].push_back({w, y});
    }
    memset(dist, INF, sizeof(dist));
    int ret = bellmanFord(1);
    if (!ret) {
        cout << "Ciclu Negativ!" << endl;
        return 0;
    }
    int num = 0;
    for (int i = 2; i <= N; i++) {
        if (num++) cout << " ";
        cout << dist[i];
    }
    cout << endl;
    return 0;
}