#include <bits/stdc++.h> 

const int kNmax = 50009;

struct Edge {
	int x;
	int y;
};

class Task {
 public:
	void solve() {
		read_input();
        get_result();
        print_output();
	}

 private:
	int n;
	int m;
	std::vector<std::pair<int, int>> adj[kNmax];
    std::vector<int> distances;
    std::vector<int> used;
    std::queue<int> q;
   
	void read_input() {
		std::ifstream fin("bellmanford.in");
		fin >> n >> m;
		for (int i = 1, x, y, cost; i <= m; i++) {
			fin >> x >> y >> cost;
			adj[x].push_back(std::pair<int, int>(cost, y));
        }

		fin.close();
	}

	bool get_result() {
        used = std::vector<int>(n + 1, 0);
        distances = std::vector<int>(n + 1, INT_MAX);
        distances[1] = 0;
        q.push(1);
        
        while (!q.empty()) {
            int node = q.front();
            used[node]++;

            if (used[node] == n) {
                return true;
            }
        
            for (auto &aux : adj[node]) {
                int adj = aux.second;
                int cost = aux.first;
                if (distances[node] + cost < distances[adj]) {
                    distances[adj] = distances[node] + cost;
                    q.push(adj);
                }
            }
            q.pop();
        }
        return false;
    }

    void print_output() {
        std::ofstream fout("bellmanford.out");
        if (get_result() == false) {
            for (int i = 2; i <=n ;i++) {
                if (distances[i] == INT_MAX) {
                    fout << "0 ";
                } else {
                    fout << distances[i] << " ";
                }
            }
            fout << "\n";
        } else {
            fout << "Ciclu negativ!\n";
        }
    }
};

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