#include <bits/stdc++.h>
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
using pii = pair<int,int>;
const int inf = 1e9+7;
const int lim = 5e4+5;
vector<pii> vec[lim];
queue<int> q;
int app[lim];
bool inq[lim];
int dist[lim];
int x,y,c;
int n,m;
int main() {
	in>>n>>m;
	for(int i=1;i<=m;++i) {
		in>>x>>y>>c;
		vec[x].push_back(make_pair(y, c));
	}
	dist[1] = 0;
	for(int i=2;i<=n;++i) {
		dist[i] = inf;
	}
	q.push(1);
	while(!q.empty()) {
		int node = q.front();
		q.pop();
		app[node]++;
		inq[node] = false;
		if(app[node] >= n) {
			out<<"Ciclu negativ!"<<'\n';
			return 0;
		}
		for(auto [x, price]: vec[node]) {
			if(dist[x] > dist[node] + price) {
				dist[x] = dist[node] + price;
				if(!inq[x]) {
					q.push(x);
					inq[x] = true;
				}
			}
		}
	}
	for(int i=2;i<=n;++i) {
		out<<dist[i]<<' ';
	}
	out<<'\n';
	return 0;
}