// 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::vector<int> distances;
    std::vector<std::pair<int, int>> adj[NMAX];
    std::queue<int> q;
    std::vector<int> used;

    bool negative_cycle;

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

        source = 1;

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


    void Bellman(int src) {
        used = std::vector<int>(N + 1, 0);
        distances = std::vector<int>(N + 1, kINF);
        distances[src] = 0;
        q.push(src);

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            used[u]++;

            if (used[u] == N) {
                negative_cycle = true;
                return;
            }

             for (auto &edge: adj[u]) {
                auto v = edge.second;
                auto w = edge.first;
                if (distances[u] != kINF && distances[v] > distances[u] + w) {
                    distances[v] = distances[u] + w;
                    q.push(v);
                }
            }
        }


        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;
	
}