// Copyright Radu Nichita 2020 [email protected] 	

#include <bits/stdc++.h>
#define NMAX 50009
#define kINF (1<<30)
#define NO_PARENT -1

using namespace std;
	
class Task {

    int N, M, source;;
    
    // std::priority_queue<pair<int, int>, vector<pair<int, int>>,
    //             greater<pair<int, int>>> pq;
    

    std::vector<int> distances;
    std::vector<std::pair<std::pair<int,int>, int>> edges;
    bool negative_cycle;

 
	
    void read_input() {
        int src, dst, cost;
        std::ifstream in("bellmanford.in");
        in >> N >> M; // dimensiune graf 
        distances = std::vector<int>(N + 1, kINF);
        for (int i = 1; i <= M; i++) {
            in >> src >> dst >> cost;
            edges.push_back({{src,dst},cost});
        }

        source = 1;

        in.close();
    }
	
 
	
    void getResult() {
        Bellman(source);
    }


    void Bellman(int src) {
        distances[src] = 0;

        for(int i = 1; i <= N - 1; i++) {
            for (auto const &edge: edges) {
                auto u = edge.first.first;
                auto v = edge.first.second;
                auto w = edge.second;
                if (distances[v] > distances[u] + w) {
                    distances[v] = distances[u] + w;
                }
            }
        }

        for (auto const &edge:edges) {
             auto u = edge.first.first;
                auto v = edge.first.second;
                auto w = edge.second;
                if (distances[v] > distances[u] + w) {
                    negative_cycle = true;
                    return ;
                }
        }

        negative_cycle = false;

    }
	
 
	
    void print() {
        std::ofstream out("bellmanford.out");  
        if (negative_cycle == false) {
            for (int i = 1; i <= N; i++) {
                if (i != source) {
                    out<<(distances[i] == kINF ? 0 : distances[i])<<" ";
            }
        }
            out<<"\n";
        } else {
            out<<"Ciclu negativ!\n";
        }
    
        out.close();
        return;
    }
	
 
	
 public:
	
    void solve() {
        read_input();
        Bellman(1);
        print();
    
    }
	
 
	
};
	
 
	
int main() {

    Task* task = new Task();
	
    task->solve();
	
    delete(task);
	
 
	
    return 0;
	
}