#include <fstream>
#include <vector>
#include <set>
#define INF 1000000001
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n, i, m, j, x, y, c;
vector <int> cost;
vector <vector<pair <int, int>>> G;
set <pair <int, int>> dk;
int main()
{
	fin >> n >> m; G.resize(n + 1); cost.resize(n + 1);
	for (i = 1; i <= m; i++)
	{
		fin >> x >> y >> c;
		G[x].push_back({ y, c });
	}
	for (i = 2; i <= n; i++)
		cost[i] = INF;
	dk.insert({ 0, 1 });
	while (!dk.empty())
	{
		c = (*dk.begin()).first;
		x = (*dk.begin()).second;
		dk.erase(dk.begin());
		for (i = 0; i < G[x].size(); i++)
		{
			if (cost[G[x][i].first] > c + G[x][i].second)
			{
				if (dk.find({ cost[G[x][i].first], G[x][i].first }) != dk.end())
					dk.erase(dk.find({ cost[G[x][i].first], G[x][i].first }));
				cost[G[x][i].first] = c + G[x][i].second;
				dk.insert({ cost[G[x][i].first], G[x][i].first });
			}
		}
	}
	for (i = 2; i <= n; i++)
		fout << cost[i] << " ";
	return 0;
}