#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::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();
}