#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
#pragma pack(1)
int D[50001];
bool viz[50001];
const int inf = 1 << 30;

struct graf
{
	int nod;
	int	cost;
};
vector <graf> v[50001];

struct compara
{
	bool operator()(int a, int b)
	{
		return D[a] > D[b];
	}
};

priority_queue<int, vector <int>, compara> heap;

int main()
{
	int n, m, a, b, c;
	in >> n >> m;
	for (int i = 0; i < m; i++)
	{
		in >> a >> b >> c;
		v[a].push_back({ b,c });
	}
	for (int i = 2; i <= n; i++) D[i] = inf;
	heap.push(1);
	viz[1] = 1;
	while (!heap.empty())
	{
		int nodcurent = heap.top();
		heap.pop();
		viz[nodcurent] = false;
		int l = v[nodcurent].size();
		int vecin;
		int COST;
		for (int i = 0; i < l; i++)
		{
			vecin = v[nodcurent][i].nod;
			COST = v[nodcurent][i].cost;
			if (D[nodcurent] + COST < D[vecin])
			{
				D[vecin] = D[nodcurent] + COST;
				if (!viz[vecin])
				{
					heap.push(vecin);
					viz[vecin] = 1;
				}
			}
		}
	}
	for (int i = 2; i <= n; i++) out << D[i] << ' ';
	return 0;
}