#include <stdio.h>
#include <vector>
#include <set>
using namespace std;

vector <pair<int, int> > graf[50001];
set <pair<int, int> > q;

long visited[50001], rez[50001], old_value, new_value, vecin, a, b, c, n, m;

int main()
{
	freopen ("dijkstra.in", "rt", stdin);
	freopen ("dijkstra.out", "wt", stdout);
	
	scanf("%ld %ld", &n, &m);
	for (long i = 1; i <= m; ++i)
	{
		scanf("%ld %ld %ld", &a, &b, &c);
		graf[a].push_back(make_pair(b, c));
	}

	for (long i = 2; i <= n; ++i)
		rez[i] = 2147000000;

	q.insert(make_pair(0, 1));
	visited[1] = 1;

	while (!q.empty())
	{
		for (long i = 0; i < graf[q.begin()->second].size(); ++i)
		{
			old_value = rez[graf[q.begin()->second][i].first];
			new_value = graf[q.begin()->second][i].second + rez[q.begin()->second];
			vecin = graf[q.begin()->second][i].first;

			if (new_value < rez[vecin])
			{
				rez[vecin] = new_value;
			}

			if (!visited[vecin])
			{	
				q.insert(make_pair(rez[vecin], vecin));
				visited[vecin] = 1;
			}
			else
			{
				if (new_value < old_value)
				{
					q.erase(q.find(make_pair(old_value, vecin)));
					q.insert(make_pair(new_value, vecin));
				}
			}
			
		}
		q.erase(q.begin());
	}

	for (long i = 2; i <= n; ++i)
		printf("%ld ", rez[i]);
	printf("\n");
	return 0;
}