#include <iostream>
#include <fstream>
#include <vector>
#include <climits>

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

const int NMAX = 50005, INF = INT_MAX;
int N, M, dist[NMAX];

struct edge{
    int u, v, cost; 
};
vector<edge> edges;
vector<int> adj[NMAX];

bool bellman(int t){
    dist[t] = 0;

    for(int i = 1; i <= N - 1; i++)
        for(auto& e : edges)    
            if(dist[e.u] < INF)
                dist[e.v] = min(dist[e.v], dist[e.u] + e.cost);

    bool ciclu = 0;
    for(auto& e : edges)    
        if(dist[e.u] < INF && dist[e.v] > dist[e.u] + e.cost)
            ciclu = 1;

    return ciclu;
}

int main(){
    f >> N >> M;
    for(int i = 1; i <= M; i++){
        int u, v, cost;
        f >> u >> v >> cost;
        edges.push_back({u, v, cost});
    }

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

    bool ok = bellman(1);

    if(ok)
        g << "Ciclu negativ!";
    else{
        for(int i = 2; i <= N; i++)
            g << dist[i] << ' ';
    }

    return 0;
}