#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <limits.h>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int N = 50005;

vector<pair<int, int>> g[N];
int CostMin[N];
bool vizitat[N];

int main()
{
	int n, m;
	fin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		fin >> a >> b >> c;
		g[a].push_back({ b, c });
	}

	for (int i = 2; i <= n; i++)
	{
		CostMin[i] = INT_MAX;
	}

	priority_queue<pair<int, int>> heap;
	heap.push({ 0, 1 });					// cost, nod

	while (!heap.empty())
	{
		int nod = heap.top().second;
		int cost = -heap.top().first;
		heap.pop();

		if (vizitat[nod])
		{
			continue;
		}

		vizitat[nod] = true;

		for (auto neigh : g[nod])
		{
			if (!vizitat[neigh.first] && cost + neigh.second < CostMin[neigh.first])
			{
				heap.push({ -(cost + neigh.second), neigh.first });
				CostMin[neigh.first] = cost + neigh.second;
			}
		}
	}

	for (int i = 2; i <= n; i++)
	{
		if (CostMin[i] == INT_MAX)
		{
			CostMin[i] = 0;
		}
		fout << CostMin[i] << ' ';
	}
}