#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
const char nl = '\n';
const char sp = ' ';
const int inf = 0x3f3f3f3f;
const int mod = 666013;
const char out[2][4]{ "NO", "YES" };
#define all(a) a.begin(), a.end()
using ll = long long;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const int nmax = 5e4;
int n, m;
vector<pair<int, int>> g[nmax + 5];
ll dist[nmax + 5]{ 0 };
int vis[nmax + 5]{ 0 };

priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    fin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        fin >> u >> v >> w;
        g[u].push_back({ v, w });
    }
    for (int i = 1; i <= n; ++i) {
        dist[i] = 1e18;
    }
    dist[1] = 0;
    pq.push({ 0, 1 });
    while (pq.size()) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        if (dist[u] != d) {
            continue;
        }
        if (++vis[u] == n) {
            fout << "Ciclu negativ!";
            return 0;
        }
        for (auto& e : g[u]) {
            int v = e.first, w = e.second;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({ dist[v], v });
            }
        }
    }
    for (int i = 2; i <= n; ++i) {
        fout << dist[i] << sp;
    }
}