#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 bellmanFordFast(int source) {
    queue<int> q;
    bitset<NMAX> inq(false);
    vector<int> countq(NMAX, 0);
    bool cycle = false;
    dist[source] = 0; q.push(source); inq[source].flip(); countq[source]++;
    while (!q.empty() && !cycle) {
        int u = q.front(); q.pop();
        inq[u] = false;
        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;
                if (!inq[v]) {
                    if (countq[v] > N) { cycle = true; break; }
                    else { q.push(v), countq[v]++, inq[v] = true; }
                }
            }
        }
    }
    return !cycle;
}

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 = bellmanFordFast(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;
}