//3. Bellman-Ford
#include <bits/stdc++.h>

using namespace std;

int n,m;
vector<pair<int,int>> adj[50001];
int dist[50001];
int main() {
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");

    fin>>n>>m;

    int a,b,c;
    for (int i=1;i<=m;i++) {
        fin>>a>>b>>c;
        adj[a].push_back({b,c});
    }

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

    dist[1]=0;

    for (int i=2;i<=n;i++) {
        for (int j=1;j<=n;j++) {
            if (dist[j]==INT_MAX) continue;

            for (auto [nod,pondere]:adj[j]) {
                if (dist[j]+pondere<dist[nod]) {
                    dist[nod]=dist[j]+pondere;
                }
            }
        }
    }

    bool ciclu_negativ = false;
    for (int i = 1; i <= n; i++) {
        if (dist[i] == INT_MAX) continue;

        for (auto [nod,pondere] : adj[i]) {
            if (dist[i] + pondere < dist[nod]) {
                ciclu_negativ = true;
                break;
            }
        }
        if (ciclu_negativ) break;
    }

    if (ciclu_negativ) {
        fout << "Ciclu negativ!";
    }
    else {
        for (int i = 2; i <= n; i++) {
            if (dist[i] == INT_MAX) fout<<0<< ' ';
            else fout<<dist[i]<< ' ';
        }
    }


}