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

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

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)
{

	for (int i = 2; i <= n; i++)
	{
		if (dist[i] == INT_MAX)
			dist[i] = 0;
		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] = INT_MAX, viz[i] = false;

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

	while(!q.empty())
	{
		int u = q.top().n;
		q.pop();

		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 (!viz[v])
				{
					if (dist[u] + cost < dist[v])
						dist[v] = dist[u] + cost, q.push({ v,dist[v] });

				}
			}
		}
	}
	printSolution(dist, n);
	delete[]viz;
	delete[]dist;
}

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 });
	}

	dijkstra(n, 1, graf);

	return 0;
}