#include <fstream>
#include <vector>
#include <tuple>
#include <limits>
#include <algorithm>

using Vertex = int;
using Distance = uint64_t;

using Edge = std::tuple<Vertex, Vertex, Distance>;

void BellmanFord(std::vector<Distance>& distances, const std::vector<Edge>& graph, int N)
{
	for (auto i = 0; i < N; ++i)
	{
		for (const auto& edge : graph)
		{
			Vertex u, v;
			Distance d;
			std::tie(u, v, d) = edge;
			distances[v - 1] = std::min(distances[v - 1], distances[u - 1] + d);
		}
	}
}
int main()
{
	std::ifstream fin("dijkstra.in");
	int N, M;
	fin >> N >> M;
	std::vector<Distance> distances(N, std::numeric_limits<Distance>::max());
	std::vector<Edge> edges;
	for (int i = 0; i < M; ++i)
	{
		Vertex u, v;
		Distance d;
		fin >> u >> v >> d;
		edges.emplace_back(u, v , d);
	}
	fin.close();
	distances[0] = 0;
	BellmanFord(distances, edges, N);
	distances.erase(distances.begin());
	std::ofstream fout("dijkstra.out");
	for (const auto d : distances)
	{
		fout << d << " ";
	}
	fout.close();
	return 0;
}