#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];

vector <pair<int, int>> graph[250001];
priority_queue <pair<int, int>> pq;

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

		graph[a].push_back({ b,weight});
	}
}

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;
	distances[1] = 0;

	pq.push({ 0,1 });
	int nod, cost;
	while(!pq.empty())
	{
		nod = pq.top().second;
		cost = -pq.top().first;
		pq.pop();
		if (distances[nod] != cost)
			continue;

		for (auto i : graph[nod])
		{
			if (distances[i.first] > distances[nod] + i.second)
			{
				distances[i.first] = distances[nod] + i.second;
				pq.push({ -distances[i.first],i.first });
			}
		}
		
	}

}




int main()
{
	

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

	input(edges);

	dijkstra(nodes,edges,1);
	
	for (int i = 2; i <= nodes; i++)
		g << (distances[i] == MAXINT ? 0 : distances[i]), g << " ";
		

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


	return 0;
}