#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef pair <int, int> pii;
typedef vector <int> vi;
typedef long long ll;
typedef unsigned long long ull;

ifstream f ("bellmanford.in");
ofstream g ("bellmanford.out");

const int NMAX = 5e4;
vector <pii> adj[NMAX];
int n, m;
int dist[NMAX], cnt[NMAX];
queue <int> q;

int main() {
    f >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v, c;
        f >> u >> v >> c;
        --u; --v;
        adj[u].pb ({v, c});
    }
    q.push (0);
    for (int i = 0; i < n; ++i) dist[i] = 1 << 30;
    dist[0] = 0;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        for (pii &p : adj[node]) {
            if (dist[p.fi] > dist[node] + p.se) {
                dist[p.fi] = dist[node] + p.se;
                if (cnt[p.fi] > n) {
                    g << "Ciclu negativ!\n"; return 0;
                }
                q.push (p.fi);
                ++cnt[p.fi];
            }
        }
    }
    for (int i = 1; i < n; ++i) {
        g << dist[i] << ' ';
    }

    f.close();
    g.close();
    return 0;
}