#include <algorithm>
#include <fstream>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

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

constexpr int INF = 1e8;
int main(){
    int n,m;
    fin>>n>>m;
    vector<vector<pair<int,int>>> lista(n+1);
    vector<int> cnt(n+1);
    vector<bool> inqueue(n+1, false);
    vector<int> dist(n+1, INF);
    for (int i = 0; i<m;i++) {
        int u,v,c;
        fin>>u>>v>>c;
        lista[u].emplace_back(v,c);
    }

    bool hasNeg = false;
    queue<int> q;
    q.push(1);
    dist[1] = 0;
    inqueue[1] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inqueue[u] = false;

        if (dist[u] != INF) {
            for (auto [v,c] : lista[u]) {
                if (dist[v] > dist[u] + c) {
                    dist[v] = dist[u] + c;
                    cnt[v]++;

                    if (cnt[v]>=n) {
                        hasNeg = true;
                        break;
                    }
                    if (!inqueue[v]) {
                        inqueue[v] = true;
                        q.push(v);
                    }
                }
            }
        }
        if (hasNeg) break;
    }
    if (hasNeg) {
        fout<<"Ciclu negativ!";
    }
    else {
        for (int i = 2;i<=n;i++) {
            fout<<dist[i]<<" ";
        }
    }
    return 0;
}