#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

#define NMax 100005
#define pb push_back
#define mp make_pair
#define inf (1<<30)+100
using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

int n, m;
vector<int> V[NMax];
vector<int> C[NMax];
int dist[NMax];
bool inq[NMax];
vector< pair<int, int> > h;

void read() {
	f>>n>>m;
	for (int i=1;i<=m;i++) {
		int a,b,c;
		f>>a>>b>>c;
		V[a].pb(b);
		C[a].pb(c);
	}
}

void solve() {
	long long pas = 0;
	while (h.size() && pas <= 1LL*n*m) {
		pas++;
		pop_heap(h.begin(), h.end());
		pair<int, int> extr = h.back();
		h.pop_back();

		int nod = extr.second;
		int cost = extr.first;

		inq[nod] = false; // L-am scos din coada
		for (unsigned i=0;i<V[nod].size();i++) {
			if (cost + C[nod][i] < dist[V[nod][i]]) {
				dist[V[nod][i]] = cost + C[nod][i];
				if (!inq[V[nod][i]]) {
					inq[V[nod][i]] = true;
					h.pb(mp(dist[V[nod][i]], V[nod][i]));
					push_heap(h.begin(), h.end());
				}
			}
		}
	}
}

bool checkneg() {

	for (unsigned i=1;i<=n;i++)
		for (unsigned j=0;j<V[i].size();j++)
			if (dist[i] + C[i][j] < dist[V[i][j]])
				return true;
	return false;
}

void init() {
	for (int i=2;i<=n;i++)
		dist[i] = inf;
	dist[1] = 0;
	h.pb(mp(0,1));
	make_heap(h.begin(), h.end());
}

int main() {

	read();
	init();
	solve();
	if (checkneg()) {
		g<<"Ciclu negativ\n";
		return 0;
	}
	for (int i=2;i<=n;i++) {
		g<<dist[i]<<' ';
	}

	f.close(); g.close();
	return 0;
}