#include <fstream>
#include <vector>
using namespace std;

#define INFINIT 10000

typedef struct _MUCHIE {
	int x, y, cost;
}MUCHIE, *PMUCHIE;

int n, m;
int distanta[50000];
vector <MUCHIE> muchii;


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

void BellmanFord(const int& n, const int& m, vector<MUCHIE> muchii, const int& sursa);


int main() {
	MUCHIE c;
	f >> n >> m;
	for (int i = 0; i < m; i++) {
		f >> c.x >> c.y >> c.cost;
		muchii.push_back(c);
	}
	BellmanFord(n, m, muchii, 1);

	return 0;
}

void BellmanFord(const int& n, const int& m, vector<MUCHIE> muchii, const int& sursa) {

	for (int i = 0; i <= n; i++)distanta[i] = INFINIT;
	
	distanta[sursa] = 0;

	for (int i = 1; i <= n - 1; i++) {
		for (auto& muchie : muchii) {
			if (distanta[muchie.x] + muchie.cost < distanta[muchie.y]) {
				distanta[muchie.y] = distanta[muchie.x] + muchie.cost;
			}
		}
	}

	for (auto& muchie : muchii) {
		if (distanta[muchie.x] + muchie.cost < distanta[muchie.y]) {
			q << "-1\n";
			return;
		}
	}
	for (int i = 2; i <= n; i++) {
		q << distanta[i] << " ";
	}

}