#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <limits.h>
using namespace std;

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


#define max_size 20000005

struct nod
{
	int n, cost;
	
};
struct compare
{
	bool operator()(const nod& a, const nod& b)
	{
		return a.cost > b.cost;
	}
};


void printSolution(int dist[], int n)
{
	/*printf("Vertex   Distance from Source\n");
	for (int i = 1; i <= n; i++)
		cout << i << "      " << dist[i] << "\n";
	*/

	for (int i = 2; i <= n; i++)
		g << dist[i] << " ";

}

void dijkstra(int n,int src, vector<vector<nod>>&graf)
{
	int* dist = new int[n + 1];
	bool* viz = new bool[n + 1];
	
	priority_queue<nod, vector<nod>,compare>q;


	for (int i = 1; i <= n; i++)
		dist[i] = max_size, viz[i] = false, q.push({ i,dist[i] });

	dist[src] = 0;
	//q.push({ src,dist[src] });

	while (!q.empty())
	{
		int u = q.top().n;
		q.pop();
		//viz[u] = 1;
		if (!viz[u])
		{
			viz[u] = 1;
			for (int i = 0; i < graf[u].size(); i++)
			{

				int v = graf[u][i].n;
				int cost = graf[u][i].cost;
				if (dist[u] != max_size and dist[u] + cost < dist[v])
					dist[v] = dist[u] + cost, q.push({ v,dist[v] });


			}
		}
	}
	printSolution(dist, n);
}

int main()
{

	int n, m;
	f >> n >> m;

	vector<vector<nod>>graf(n+1);

	for (int i = 1; i <= m; i++)
	{
		int x, y, z;
		f >> x >> y >> z;
		graf[x].push_back({ y,z });
		//graf[y].push_back({ x,z });
	}

	dijkstra(n, 1, graf);
	

	return 0;
}