#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector <pair <int, int> > a[50005];
bitset <50005> viz;
priority_queue <pair<int, int> > Q; /// cost, nod
int dp[50005];
int n, m;

void Dijkstra(int x)
{
	for (int i = 1; i <= n; i++)
		dp[i] = INF;
	dp[x] = 0;
	Q.push({ 0, x });
	while (!Q.empty())
	{
		x = Q.top().second;
		Q.pop();
		if (viz[x] == 0)
		{
			viz[x] = 1;
			for (auto w : a[x])
				{
					if (dp[w.second] > dp[x] + w.first)
					{
						dp[w.second] = dp[x] + w.first;
						Q.push({ -dp[w.second], w.second });
					}
				}
		}
	}
}

int main()
{
	int i, j, x, y, c;
	fin >> n >> m;
	while (m--)
	{
		fin >> x >> y >> c;
		a[x].push_back({ c, y });
	}

	Dijkstra(1);
	for (i = 2; i <= n; i++)
		if (dp[i] == INF)
			fout << "0 ";
		else fout << dp[i] << " ";
	return 0;
}