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


const int NMAX = 50005;
const int INF  = LLONG_MAX;

std::vector< std::pair<int, int> > Graf[NMAX];
long long int dist[NMAX];
std::queue<int> Coada;
int frecv[NMAX];

std::ofstream out("bellmanford.out");


void init_dist(int N, int rad) {

	for (int i = 1; i <= N; ++i) {
		dist[i] = INF;
	}

	dist[rad] = 0;
}


void Bellman_Ford(int N, int M, int rad) {

	Coada.push(rad);

	do {

		int nod_curent = Coada.front();
		Coada.pop();

		++frecv[nod_curent];
		if (frecv[nod_curent] > N) {
			out << "Ciclu negativ!\n";
			return;
		}

		for (int i = 0; i < Graf[nod_curent].size(); ++i) {
			int Vecin = Graf[nod_curent][i].first;
			int Cost = Graf[nod_curent][i].second;

			if (dist[nod_curent] + Cost < dist[Vecin]) {
				dist[Vecin] = dist[nod_curent] + Cost;
				Coada.push(Vecin);
			}
		}

	} while (!Coada.empty());

	for (int i = 2; i <= N; ++i) {
		out << dist[i] << ' ';
	}
}


int main() {
	
	std::ifstream in("bellmanford.in");

	int N, M;
	in >> N >> M;

	for (int i = 1; i <= M; ++i) {
		int nod1, nod2, cost;
		in >> nod1 >> nod2 >> cost;
		Graf[nod1].push_back(std::make_pair(nod2, cost));
	}

	int rad = 1;
	init_dist(N, rad);

	Bellman_Ford(N, M, rad);
	return 0;
}