#include <iostream>
#include <vector>
#include <fstream>
#include <set>
#include <utility>
#include <climits>

using namespace std;

ifstream be("bellmanford.in");
ofstream ki("bellmanford.out");


void beolvas(vector<vector<pair<int, int>>>& graf, int m);
void legrovidebb_ut(const vector<vector<pair<int, int>>>& graf, int n, int start);
bool bellman_ford(const vector<vector<pair<int, int>>>& graf, int n, int start, vector<int> &d, vector<int> &p);
void relax(const vector<vector<pair<int, int>>>& graf, int v, vector<int>& d, vector<int>& p);
void bellman_ut(int v, vector<int>& d, vector<int>& p);

int main(){
	int n, m, start;
	be >> n >> m;
	start = 0;
	//be >> n >> m >> start;
	//start--;
	vector<vector<pair<int, int>>> graf(n);
	beolvas(graf, m);
	legrovidebb_ut(graf, n, start);
}

void beolvas(vector<vector<pair<int, int>>>& graf, int m) {
	for (int i = 0; i < m; i++) {
		int x, y, z;
		be >> x >> y >> z;
		graf[x - 1].push_back(make_pair((y - 1), z));
	}
}

void legrovidebb_ut(const vector<vector<pair<int, int>>>& graf, int n, int start) {
	vector<int> d(n, INT_MAX);
	vector<int> p(n, -1);

	if (bellman_ford(graf, n, start, d, p)) {
		//ki << "Van negativ kor";
		ki << "Ciclu negativ!";
	}
	else {
		for (int i = 0; i < n; i++) {
			if (i != start) {
				if (d[i] != INT_MAX) {
					ki << d[i] << " ";
					//ki << "A legrovidebb ut hossza " << i+1 << "-ba/be: " << d[i] << "\n";
					//ki << "A legrovidebb ut " << i+1 << "-ba/be: ";
					//bellman_ut(i, d, p);
				}
				else{
					//ki << "A legrovidebb ut hossza " << i+1 << "-ba/be: Nem lehet eljutni!\n";
					//ki << "A legrovidebb ut " << i+1 << "-ba/be: Nem lehet eljutni!\n";
				}
			}
		}
	}
}

bool bellman_ford(const vector<vector<pair<int, int>>>& graf, int n, int start, vector<int>& d, vector<int>& p) {
	d[start] = 0;

	for (int i = 0; i < n-1; i++)
		for (int u = 0; u < n; u++)
			relax(graf, u, d, p);

	for (int u = 0; u < n; u++)
		for (auto i : graf[u]) {
			int w = i.first;
			if ((d[u] != INT_MAX) && (d[w] > (d[u] + i.second)))
				return true;		
		}
	return false;
}

void relax(const vector<vector<pair<int, int>>>& graf, int v, vector<int>& d, vector<int>& p) {
	for (auto i : graf[v]) {
		int w = i.first;
		if ((d[v] != INT_MAX) && (d[w] > (d[v] + i.second))) {
			d[w] = d[v] + i.second;
			p[w] = v;
		}
	}
}

void bellman_ut(int v, vector<int>& d, vector<int>& p) {
	vector<int> ut;
	ut.push_back(v);
	while (p[ut[ut.size() - 1]] != -1) {
		ut.push_back(p[ut[ut.size() - 1]]);
	}

	for (int i = ut.size() - 1; i >= 0; i--) {
		ki << ut[i] + 1 << " ";
	}
	ki << "\n";
}