#include <bits/stdc++.h>

using namespace std;

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

const int maxN = 5e4 + 5;
const int INF = 1e18;

int fr[maxN], dist[maxN];
bool inQ[maxN];

vector <pair<int,int>> g[maxN];

signed main() {

    int n, m; fin >> n >> m;

    for(int i = 1; i <= m; ++i) {
        int u, v, cost; fin >> u >> v >> cost;

        g[u].push_back({v, cost});
    }

    for(int i = 1; i <= n; ++i) dist[i] = INF;

    queue <int> q;

    q.push(1);
    dist[1] = 0;

    while(! q.empty()) {
        int node = q.front();

        q.pop();

        fr[node] ++;
        if(fr[node] == n) {
            fout << "Ciclu negativ!";
            return 0;
        }

        inQ[node] = false;

        for(auto to : g[node]) {
            int next = to.first;
            int cost = to.second;

            if(dist[next] > dist[node] + cost) {
                dist[next] = dist[node] + cost;
                if(inQ[next] == false) {
                    inQ[next] = true;
                    q.push(next);
                }
            }
        }
    }

    for(int i = 2; i <= n; ++i)
        fout << dist[i] << " ";

    return 0;
}