#include <fstream>
#include <limits>
#include <iomanip>

std::ifstream f("dijkstra.in");
std::ofstream g("dijkstra.out");

constexpr int INF = std::numeric_limits<int>::max();

int numNodes, numArcs;
int * graph[50001], distance[50001];
bool visited[50001] = { false };

void Read()
{
	f >> numNodes >> numArcs;

	int i, nod1, nod2, dist;

	for (i = 1; i <= numNodes; ++i) {
		graph[i] = new int[50001];
	}
	
	for (i = 1; i <= numArcs; ++i) {
		f >> nod1 >> nod2 >> dist;

		graph[nod1][nod2] = dist;
		distance[i] = INF;
	}
}

void Init()
{
	for (int i = 2; i <= numNodes; ++i)
		if (graph[1][i] >= 0)
			distance[i] = graph[1][i];

	visited[1] = true;
}

void Dijkstra()
{
	for (int i = 2; i <= numNodes; ++i) {
		for (int j = 1; j <= numNodes; ++j) {
			if (graph[i][j] >= 0 && !visited[j] && distance[i] + graph[i][j] < distance[j]) {
				distance[j] = distance[i] + graph[i][j];
			}
		}
		visited[i] = true;
	}
}

void Print()
{
	for (int j = 2; j <= numNodes; ++j)
		g << distance[j] << ' ';
}

int main(int argc, char * argv[])
{
	Read();
	Init();
	Dijkstra();
	Print();

	return 0;
}