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

int main()
{
	ifstream fin("bellmanford.in");
	ofstream fout("bellmanford.out");
	int n, m;
	fin >> n >> m;
	vector<pair<int,int> > adjl[n+1];
	vector<pair<int,int> >::iterator it;
	int u, v, w;
	for (; m > 0; --m) {
		fin >> u >> v >> w;
		adjl[u].push_back(pair<int,int>(v,w));
	}
	const int inf = 1e9;
	int dist[n+1];
	int cnt[n+1];
	bool inq[n+1];
	queue<int> q;
	dist[1] = 0;
	for (int i = 2; i <= n; ++i) {
		dist[i] = inf;
		cnt[i] = 0;
		inq[i] = false;
	}
	q.push(1);
	while (!q.empty()) {
		u = q.front();
		q.pop();
		inq[u] = false;
		for (it = adjl[u].begin(); it != adjl[u].end(); ++it) {
			v = it->first;
			if (dist[v] > dist[u]+it->second) {
				dist[v] = dist[u]+it->second;
				if (!inq[v]) {
					q.push(v);
					inq[v] = true;
					if (++cnt[v] == n) {
						fout << "Ciclu negativ!";
						return 0;
					}
				}
			}
		}
	}
	for (int i = 2; i <= n; ++i)
		fout << dist[i] << ' ';
	return 0;
}