#include <fstream>
#include <vector>

#define NMax 50010
#define INF 2000000000

using namespace std;

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

int nodes, edges, QU[NMax], passes[NMax], qfront, qback, distances[NMax];
vector< pair<int, int> > G[NMax];

void BellmanFord(int node)
{
	for (int i = 1; i <= nodes; i++)
		distances[i] = INF;
	distances[node] = 0;

	qfront = 1, qback = 0;
	QU[++qback] = node;
	passes[node] = 1;

	while (qfront <= qback) {
		int crtNode = QU[qfront];
		qfront++;

		passes[crtNode]++;
		if (passes[crtNode] > nodes) {
			g << "Ciclu negativ!";
			return;
		}

		for (vector< pair<int, int> >::iterator it = G[crtNode].begin(); it != G[crtNode].end(); it++) {
			if (distances[it->first] > distances[crtNode] + it->second) {
				distances[it->first] = distances[crtNode] + it->second;
				QU[++qback] = it->first;
			}
		}
	}

	for (int i = 2; i <= nodes; i++)
		g << distances[i] << " ";
}

int main()
{
	f >> nodes >> edges;

	int n1, n2, c;
	for (int i = 1; i <= edges; i++) {
		f >> n1 >> n2 >> c;

		G[n1].push_back(make_pair(n2, c));
	}

	BellmanFord(1);

	return 0;
}