#include<fstream>
#include<vector>
#include<queue>
#define pii std::pair<int, int>

std::ifstream fin("bellmanford.in");
std::ofstream fout("bellmanford.out");

int n, m;
bool has_negative_cycle; //o folosim ca sa stim cand oprim programul, pentru a evita un ciclu infinit
std::vector<std::vector<pii> > G; //se face un artificiu pentru a stoca pentru fiecare vecin si costul asociat muchiei

struct comp {
	bool operator()(pii a, pii b) {
		return a.second < b.second;
	}
};

void BellmanFord(int start) {
	std::vector<int> D(n + 1, 0x3f3f3f3f); //0x3f3f3f3f este un miliard si ceva, suficient ca inmultit cu 2 sa nu dea overflow la tipul de date int
	std::priority_queue<pii, std::vector<pii>, comp> PQ;
	std::vector<bool> viz(n + 1, false); //noteaza daca elementul e in coada la un moment dat
	std::vector<int> iq(n + 1, 0); //noteaza de cate ori intra elementul in coada

	D[start] = 0; //logic ca distanta de la un nod la el insusi e 0
	viz[start] = 1;
	++iq[start];
	PQ.push({ start, 0 });

	while (!PQ.empty()) {
		pii curr = PQ.top();
		viz[curr.first] = 0;
		PQ.pop();

		for (const pii& vecin : G[curr.first])
			if (D[vecin.first] > D[curr.first] + vecin.second and !viz[vecin.first]) {
				D[vecin.first] = D[curr.first] + vecin.second;
				viz[vecin.first] = true;
				PQ.push({ vecin.first, D[vecin.first] });
				if (++iq[vecin.first] > n) {
					has_negative_cycle = true;
					return; //programul se opreste, am gasit ciclu negativ
				}
			}
	}

	for (int i = 2; i <= n; ++i)
		if (D[i] == 0x3f3f3f3f)
			fout << -1 << ' ';
		else
			fout << D[i] << ' ';
}

int main() {
	fin >> n >> m;

	int x, y, c;

	G.resize(n + 1);

	for (; fin >> x >> y >> c;)
		G[x].push_back({ y, c });

	BellmanFord(1);

	if (has_negative_cycle)
		fout << "Ciclu negativ!";
}