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

using namespace std;

ifstream input("bellmanford.in");
ofstream output("bellmanford.out");

const int INF = 1 << 30;

struct Edge
{
    int u;
    int v;
    int cost;
};

int bellmanFord(vector<Edge> &edges, vector<int> &dist, int N, int M)
{
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            int u = edges[j].u;
            int v = edges[j].v;
            int cost = edges[j].cost;
            if(dist[v] > dist[u] + cost){
                if(i == N-1){
                    return -1;
                }
                dist[v] = dist[u] + cost;
            }
        }
    }
    return 0;
}

int main()
{
    int N, M;
    input >> N >> M;
    vector<Edge> edges(M);

    for(int i = 0; i < M; i++){
        int u, v, cost;
        input >> u >> v >> cost;
        edges[i] = {u-1, v-1, cost};
    }

    vector<int> dist(N, INF);
    dist[0] = 0;

    int sol = bellmanFord(edges, dist, N, M);
    if(sol == -1){
        output << "Ciclu negativ!";
    }else {
        for(int i = 1; i < N; i++){
            output << dist[i] << " ";
        }
    }
    return 0;
}