#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

typedef std::pair<int, int> int_pair;

inline int read() {
	int n = 0;
	bool neg = false;
	char c = getchar_unlocked();
	if (c == '-') {
		neg = true;
	}
	while (!('0' <= c && c <= '9')) {
		c = getchar_unlocked();
	}

	while ('0' <= c && c <= '9') {
		n = (n << 3) + (n << 1) + c - '0';
		c = getchar_unlocked();
	}

	if (neg) {
		return n *= -1;
	}

	return n;
}

inline void print(int n) {
	char snum[65];
	int i = 0, semn = 1;

	if (n < 0) {
		semn = -1;
	}

	do {
		snum[i++] = (semn * n) % 10 + '0';
		n /= 10;
	} while (n);

	--i;

	if (semn == -1) {
		putchar('-');
	}

	while (i >= 0) {
		putchar(snum[i--]);
	}

	putchar(' ');
}

class Graph {
private:
	int nr_nodes;
	std::vector<std::pair<int, int>> *adj;
public:
	Graph(int nr_nodes) {
		this->nr_nodes = nr_nodes;
		adj = new std::vector<int_pair> [nr_nodes];
	}

	~Graph() {
		delete [] adj;
	}

	void addEdge(int src, int dest, int cost) {
		adj[src].push_back(std::make_pair(dest, cost));
	}

	void bellmanford(int src) {
		std::queue<int> q;
		std::vector<int> dist(nr_nodes, INF), cnt_q(nr_nodes, 0);
		std::vector<bool> visited(nr_nodes, false);
		bool negative_cycle = false;
		dist[0] = 0;
		q.push(0);
		visited[0] = true;


		while (!q.empty() && !negative_cycle) {
			int node_src = q.front();
			q.pop();
			visited[node_src] = false;
			for (auto& it : adj[node_src]) {
				int node_dest = it.first;
				int w = it.second;
				
				if (dist[node_dest] > dist[node_src] + w) {
					dist[node_dest] = dist[node_src] + w;
					if (!visited[node_dest]) {
						if (cnt_q[node_dest] == nr_nodes) {
							negative_cycle = true;
						} else {
							q.push(node_dest);
							visited[node_dest] = true;
							++cnt_q[node_dest];
						}
					}
				} 
			}
		}

		if (!negative_cycle) {
			for (int i = 1 ; i < nr_nodes ; ++i) {
				print(dist[i]);
			}
		} else {
			printf("Ciclu negativ!\n");
		}
	}
};

int main() {
	freopen("bellmanford.in", "r", stdin);
	freopen("bellmanford.out", "w", stdout);

	int n, m, src, dest, cost;
	n = read(), m = read();

	Graph graph(n);
	for (; m ; --m) {
		src = read(), dest = read(), cost = read();
		graph.addEdge(src - 1, dest - 1, cost);
		// print(src), print(dest), print(cost);
		// putchar('\n');
	}

	graph.bellmanford(0);

	return 0;
}