#include <bitset>
#include <queue>
#include <vector>
#include <fstream>
using namespace std;
vector<pair<int,int>> No[50000];
const int inf = 1 << 30;
int d[50001],cnt[50001],N, M;
bitset<50001> v,in;
ifstream f("bellmanford.in");
ofstream of("bellmanford.out");
bool neg;
void bf(const int& a){
	queue<int> q;
	q.push(a);
	v[a] = 1;
	d[a] = 0;
	while (!q.empty()){
		int x = q.front();
		q.pop();
		in[x] = 0;
		for (auto& j : No[x])
		if (!v[j.first] || d[j.first]>d[x]+j.second){
			v[j.first] = 1;
			d[j.first] = d[x] + j.second;
			++cnt[j.first];
			if (cnt[j.first] > N){
				neg = 1; return;
			}
			if (!in[j.first]) q.push(j.first), in[j.first] = 1;
		}
	}
}
int main(){
	f >> N >> M;
	int a, b, c;
	for (int i = 2; i <= N; ++i)
		d[i] = inf;
	for (int i = 0; i < M; ++i){
		f >> a >> b >> c;
		No[a].push_back(make_pair(b, c));
	}
	bf(1);
	if (neg)of<<"Ciclu negativ!";
	else
	for (int i = 2; i <= N; ++i)
		of << d[i] << " ";
}