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

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

struct Vertex
{
	int parent;
	int cost;

	Vertex(int parent, int cost)
	{
		this->parent = parent;
		this->cost = cost;
	}
};

class Graph
{
private:
	static const int oo = (1 << 30) - 1;
	int VerticesNumber;
	std::list < Vertex >* Vertices;
public:
	Graph(int VerticesNumber)
	{
		this->VerticesNumber = VerticesNumber;
		Vertices = new std::list < Vertex >[VerticesNumber];
	}

	void AddEdge(int vertex1, int vertex2, int cost)
	{
		Vertices[vertex1].push_back(Vertex(vertex2, cost));
	}

	void Dijkstra();
};

class Comparison
{
public:
	bool operator() (const Vertex& a, const Vertex& b)
	{
		return a.cost > b.cost;
	}
};

void Graph::Dijkstra()
{
	std::priority_queue < Vertex, std::vector<Vertex>, Comparison > pq;

	int source = 1;

	std::vector < int > distance(VerticesNumber, Graph::oo);
	std::vector < bool > visited(VerticesNumber, false);

	pq.push(Vertex(source, 0));
	distance[source] = 0;

	while (!pq.empty())
	{
		int NodCurent = pq.top().parent;
		pq.pop();

		visited[NodCurent] = true;

		std::list<Vertex>::iterator i;
		for (i = Vertices[NodCurent].begin(); i != Vertices[NodCurent].end(); i++)
		{
			int TempVertex = (*i).parent;
			int TempCost = (*i).cost;

			if (visited[TempVertex] == false and distance[TempVertex] > distance[NodCurent] + TempCost)
			{
				distance[TempVertex] = distance[NodCurent] + TempCost;
				pq.push(Vertex(TempVertex, TempCost));
			}
		}
	}

	for (int i = 2; i < VerticesNumber; i++)
		out << distance[i] << " ";
}

int main()
{
	int N, M;
	in >> N >> M;

	Graph g(N + 1);

	int tempV1, tempV2, tempC;
	for (int it = 0; it < M; it++)
	{
		in >> tempV1 >> tempV2 >> tempC;
		g.AddEdge(tempV1, tempV2, tempC);
	}

	g.Dijkstra();
}