#include <fstream>
#include <queue>
#include <vector>
 
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::vector < Vertex >* Vertices;
public:
	Graph(int VerticesNumber)
	{
		this->VerticesNumber = VerticesNumber;
		Vertices = new std::vector < 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;
 
	int times = 0;
 
	while (!pq.empty() or times == VerticesNumber)
	{
		int NodCurent = pq.top().parent;
		pq.pop();
 
		visited[NodCurent] = true;
		times++;
 
		std::vector<Vertex>::iterator i;
		for (i = Vertices[NodCurent].begin(); i != Vertices[NodCurent].end(); i++)
		{
			int TempVertex = (*i).parent;
			int TempCost = (*i).cost;
 
			int CostSalt = distance[NodCurent] + TempCost;
 
			if (CostSalt < distance[TempVertex])
			{
				distance[TempVertex] = CostSalt;
				if(visited[TempVertex] == false)
					pq.push(Vertex(TempVertex, CostSalt));
			}
		}
	}
 
	for (int i = 2; i < VerticesNumber; i++)
	{
		if (distance[i] != Graph::oo)
			out << distance[i] << " ";
		else
			out << "0 ";
	}
		
}
 
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();
}