#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <time.h>
#include <queue>

#define MAXINT 0x7FFFFFFF

using namespace std;

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


int distances[50001];

struct node
{
	int id;
	int distance;
	bool operator<(const node& rhs) const
	{
		return distance > rhs.distance;
	}
};

struct adjNode
{
	int nodeId;
	int weight;
	
};
vector<adjNode> graph[250001];
priority_queue <node> pq;

void input(int edges)
{
	for (int i = 1; i <= edges; i++)
	{
		int a = 0, b = 0, weight = 0;
		f >> a >> b >> weight;
		adjNode node;
		node.nodeId = b;
		node.weight = weight;

		graph[a].push_back(node);
	}
}

void dijkstra(int nodes, int edges,int startNode)
{
	///determines the minimum distance from the source node to each node
	

	for (int i = 1; i <= nodes; i++)
		distances[i] = MAXINT;
	
	node start;
	start.id = startNode;
	start.distance = 0;
	pq.push(start);

	while(!pq.empty())
	{
		
		node crtnode = pq.top();
		pq.pop();

		for (auto adjNode : graph[crtnode.id])
		{
			if (distances[adjNode.nodeId] > crtnode.distance + adjNode.weight)
			{
				distances[adjNode.nodeId] = crtnode.distance + adjNode.weight;
				node thisNode;
				thisNode.id = adjNode.nodeId;
				thisNode.distance = distances[adjNode.nodeId];
				pq.push(thisNode);
			}
		}
		
	}

}




int main()
{
	

	
	
	int nodes = 0, edges = 0;
	f >> nodes >> edges;

	input(edges);

	dijkstra(nodes,edges,1);

	for (int i = 2; i <= nodes; i++)
		if (distances[i] == MAXINT)
			g << "0 ";
		else
			g << distances[i] << " ";

	
	
	f.close();
	g.close();


	
	
	return 0;
}