#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define F first
#define S second
#define endl '\n'
#define all(a) (a).begin(),(a).end()
using namespace std;
const int maxn = 50005;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

bool bellman_ford(int source, const vector<vector<pair<int, int>>>& adj, vector<int>& d) {
    int n = adj.size();
    vector<int> counter(n, 0);
    vector<char> inqueue(n, 0);
    queue<int> q;

    d[source] = 0;
    q.push(source);
    inqueue[source] = 1;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        inqueue[v] = 0;
        for (auto u : adj[v]) {
            int to = u.first;
            int dist = u.second;
            if (d[v] + dist < d[to]) {
                d[to] = d[v] + dist;
                if (!inqueue[to]) {
                    q.push(to);
                    inqueue[to] = 1;
                    counter[to]++;
                    if (counter[to] > n) {
                        return 0;
                    }
                }
            }
        }
    }
    return true;
}

void solve() {
    int n, m;
    fin >> n >> m;
    vector<vector<pair<int, int>>> adj(n, vector<pair<int, int>>());
    while (m--) {
        int x, y, c;
        fin >> x >> y >> c;
        x--;
        y--;
        adj[x].pb({y, c});
    }
    vector<int> d(n, 5 * maxn);
    if (!bellman_ford(0, adj, d)) {
        fout << "Ciclu negativ!" << endl;
    }
    else {
        for (int i = 1; i < n; i++) {
            fout << d[i] << " ";
        }
        fout << endl;
    }
}
 
int main() {
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}