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

using namespace std;

#define NMAX 100100
#define MMAX 250200
#define INF 1000000

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

vector < pair < int, int > > graf[NMAX];
int viz[NMAX], cost[NMAX], n, m, frecventa[NMAX];


struct compara
{
	bool operator()(int x, int y)
	{
		return cost[x] > cost[y];
	}
};

priority_queue<int, vector<int>, compara> C;

void citireGraf()
{
	int x, y, c;
	for (int i = 0; i < m; i++)
	{
		f >> x >> y >> c;
		graf[x].push_back(make_pair(y, c));
	}
}

void init(int x)
{
	for (int i = 1; i <= n; i++)
	{
		viz[i] = 0;
		cost[i] = INF;
	}
	cost[x] = 0;
}

int dijkstra(int nodStart)
{
	init(nodStart);
	C.push(nodStart);
	viz[nodStart] = 1;

	while (C.empty()!=true)
	{
		int nodCurent = C.top();
		C.pop();
		viz[nodCurent] = 0;
		frecventa[nodCurent]++;
		if (frecventa[nodCurent] > m)
		{
			g << "Ciclu negativ!\n";
			return 0;
		}
		int lim = graf[nodCurent].size();

		for (int i = 0; i < lim; i++)
		{
			int vecin = graf[nodCurent][i].first;
			int cos = graf[nodCurent][i].second;
			if (cost[nodCurent] + cos < cost[vecin])
			{
				cost[vecin] = cost[nodCurent] + cos;
				if (viz[vecin] == 0)
				{
					C.push(vecin);
					viz[vecin] = 1;
				}
			}
		}
	}

	return 1;
}

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

	citireGraf();

	int ok = dijkstra(1);

	if (ok == 1)
	{
		for (int i = 2; i <= n; i++)
		{
			g << cost[i] << " ";
		}
	}
	return 0;
}