#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

const int kNmax = 50005;
const int inf = 10000000;

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

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

 private:
	int n;
	int m;
	vector<edge> graph;

	void read_input() {
		ifstream fin("bellmanford.in");
		fin >> n >> m;
        edge e;

		for (int i = 1; i <= m; i++) {
			fin >> e.u >> e.v >> e.cost;
			graph.push_back(e);
		}
		fin.close();
	}

	void get_result() {
		vector<int> d(n+1);

        for (int i = 1; i <= n; i++) {
            d[i] = inf;
        }
        d[1] = 0;

        for (int i = 1; i <= n - 1; i++) {
            for (int j = 0; j < m; j++) {
                if (d[graph[j].u] != inf && d[graph[j].u] + graph[j].cost < d[graph[j].v]) {
                    d[graph[j].v] = d[graph[j].u] + graph[j].cost;
                }
            }
        }

        ofstream fout("bellmanford.out");

        for (int j = 0; j < m; j++) {
            if (d[graph[j].u] != inf && d[graph[j].u] + graph[j].cost < d[graph[j].v]) {
                fout << "Ciclu negativ!";
                return;
            }
        }

        for (int i = 2; i <= n; i++) {
			fout << d[i] << ' ';
		}
        
        fout << '\n';
		fout.close();
	}
};

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