#include <iostream>
#include <fstream>
using namespace std;

#define MAX_N 50001
#define MAX_M 250001
#define INF 1<<30
struct graph
{
	int node, cost;
	graph *next;
};

graph *el[MAX_N];
int n, m,k;

int poz[MAX_N], h[MAX_N], dist[MAX_N];

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

void swap(int a, int b)
{
	int temp = h[a];
	h[a] = h[b];
	h[b] = temp;
}

void add(int a, int node, int cost)
{
	graph *temp = new graph;
	temp->node = node;
	temp->cost = cost;
	temp->next = el[a];
	el[a] = temp;
}


void down_heap(int p)
{
	int f;
	while (p <= k)
	{
		f = p;
		if ((p << 1) <= k)
		{
			f = p << 1;
			if (f + 1 <= k)
			{
				if (dist[h[f + 1]] < dist[h[f]]) f++;
			}
		}
		else return;
		if (dist[h[f]] < dist[h[p]])
		{
			poz[h[f]] = p;
			poz[h[p]] = f;
			swap(f, p);
			p = f;
		}
		else return;
	}
}


void up_heap(int p)
{
	int f;
	while (p > 1)
	{
		f = p >> 1;
		if (dist[h[p]] < dist[h[f]])
		{
			poz[h[f]] = p;
			poz[h[p]] = f;
			swap(f, p);
			p = f;
		}
		else p = 1;
	}
}


void readData()
{
	int i, a, b, c;
	f >> n >> m;
	for (i = 0; i < m; i++)
	{
		f >> a >> b >> c;
		add(a, b, c);
	}
}


void Djikstra_Solve()
{
	int i,min;
	for (i = 2; i <= n; i++)
	{
		dist[i] = INF;
		poz[i] = -1;
	}
	h[++k] = 1;
	poz[1] = 1;

	while (k)
	{
		min = h[1];
		swap(1, k);
		poz[h[1]] = 1;
		--k;

		down_heap(1);

		graph *q = el[min];

		while (q)
		{
			if (dist[q->node] > dist[min] + q->cost)
			{
				dist[q->node] = dist[min] + q->cost;

				if (poz[q->node] != -1)
				{
					up_heap(poz[q->node]);
				}
				else
				{
					h[++k] = q->node;
					poz[h[k]] = k;
					up_heap(k);
				}
			}
			q = q->next;
		}

	}
}


int main()
{
	readData();
	Djikstra_Solve();
	for (int i = 2; i <= n; i++)
	{
		g << ((dist[i] == INF) ? 0 : dist[i])<<" ";
	}
	f.close();
	g.close();
	return 0;
}