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

#define NMax 50010
#define INF 1000000000

using namespace std;

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

int nodes, edges, passes[NMax], dist[NMax];
vector< pair<int, int> > G[NMax];
queue < pair<int, int> > QU;

bool BellmanFord(int source)
{
	for (int i = 1; i <= nodes; i++)
		dist[i] = INF;
	dist[source] = 0;

	QU.push(make_pair(source, 0));
	while (!QU.empty()) {
		pair<int, int> crtNode = QU.front();
		QU.pop();

		passes[crtNode.first]++;

		if (passes[crtNode.first] > nodes)
			return true;

		for (auto node : G[crtNode.first]) {
			if (dist[node.first] > dist[crtNode.first] + node.second) {
				dist[node.first] = dist[crtNode.first] + node.second;
				QU.push(make_pair(node.first, dist[node.first]));
			}
		}
	}
}

int main()
{
	f >> nodes >> edges;
	int n1, n2, cost;
	for (int i = 1; i <= edges; i++) {
		f >> n1 >> n2 >> cost;
		G[n1].push_back(make_pair(n2, cost));
	}

	if (!BellmanFord(1))
		g << "Ciclu negativ!";
	else
		for (int i = 2; i <= nodes; i++)
			g << dist[i] << ' ';

	
}