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

#define SIZE 25000
#define INF 999999

using namespace std;

ifstream fin("bellmanford.txt");

vector< pair<int, int> > graf[SIZE];
int n, m;
int lungime[SIZE];
int viz[SIZE];
queue<int> coada;
bool inCoada[SIZE];

void citire() {
	fin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y, cost;
		fin >> x >> y >> cost;
		graf[x].push_back(make_pair(y, cost));
	}
}

bool bellmanford(int sursa) {
	for (int i = 1; i <= n; i++) {
		lungime[i] = INF;
	}
	lungime[sursa] = 0;
	coada.push(sursa);
	inCoada[sursa] = true;

	while (!coada.empty()) {
		int x = coada.front();
		viz[x]++;
		if (viz[x] >= n) {
			return false;
		}
		coada.pop();
		inCoada[x] = false;
		for (unsigned int i = 0; i < graf[x].size(); i++) {
			int y = graf[x][i].first;
			int cost = graf[x][i].second;
			if (lungime[x] + cost < lungime[y]) {
				lungime[y] = lungime[x] + cost;
				if (inCoada[y] == false) {
					coada.push(y);
					inCoada[y] = true;
				}
			}
		}
	}
	return true;
}

int main() {
	citire();
	
	int sursa;
	cout << "Introduceti nodul sursa: ";
	cin >> sursa;

	if (bellmanford(sursa)) {
		for (int i = 1; i <= n; i++) {
			if (i != sursa) {
				cout << lungime[i] << " ";
			}
		}
	}
	else {
		cout << "Ciclu negativ!" << endl;
	}

	while (1);
	return 0;
}