#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int INF = 0x7fffffff;
const int NMAX = 50000 + 1;

int n;
int vizitat[NMAX];
int d[NMAX];
vector <int> graf[NMAX];
vector <int> cost[NMAX];

void citeste() {
	int m, a, b, c;
	f >> n >> m;

	while(m--) {
		f >> a >> b >> c;
		graf[a].push_back(b);
		cost[a].push_back(c);
	}
}

bool bellman_ford(int sursa) {
	for (int i = 1; i <= n; i++) d[i] = INF;
	d[sursa] = 0;

	queue <int> q;
	q.push(sursa);

	while (!q.empty()) {
		int nod = q.front();
		q.pop();

		vizitat[nod]++;
		if (vizitat[nod] > n) {
			g << "Ciclu negativ!\n";
			return false;
		}

		int l = graf[nod].size();
		for (int i = 0; i < l; i++) {
			int fiu = graf[nod][i];
			int d_crt = cost[nod][i] + d[nod];
			if (d_crt < d[fiu]) {
				d[fiu] = d_crt;
				q.push(fiu);
			}
		}
	}

	return true;
}

void scrie() {
	for (int i = 2; i <= n; i++) g << d[i] << ' ';
	g << '\n';
}

int main() {
	citeste();
	if (bellman_ford(1)) scrie();
	return 0;
}