// Heap

#include <fstream>
#include <vector>

using namespace std;

#define maxN 50005
#define PB push_back
#define MP make_pair
#define inf (1 << 30)

int N, M, dim;
int H[maxN];
vector < pair <int, int> > lista[maxN];
bool cont[maxN];
int cost[maxN], poz[maxN];


void push (int nod)
{
	if (nod == 1) return;
	if ( cost[ H[nod / 2] ] <= cost[ H[nod] ] ) return;
	
	swap (H[nod], H[nod / 2]);
	swap (poz[H[nod]], poz[H[nod / 2]]);
	
	push (nod / 2);
}


void pop (int nod)
{
	int nodmin = nod, st = 2 * nod, dr = 2 * nod + 1;
	
	if (st <= dim && cost[H[st]] < cost[H[nodmin]]) nodmin = st;
	if (dr <= dim && cost[H[dr]] < cost[H[nodmin]]) nodmin = dr;
	
	if (nodmin == nod) return;
	
	swap (H[nod], H[nodmin]);
	swap (poz[H[nod]], poz[H[nodmin]]);
	
	pop (nodmin);
}


int main()
{
	ifstream f ("dijkstra.in");
	ofstream g ("dijkstra.out");
	
	f >> N >> M;
	
	while (M --)
	{
		int a, b, c;
		
		f >> a >> b >> c;
		
		lista[a]. PB ( MP (b, c) );
	}
	
	
	H[++ dim] = 1;
	poz[1] = 1;
	
	for (int i = 2; i <= N; ++ i)
	{
		cost[i] = inf;
		
		H[++ dim] =  i;
		
		poz[i] = dim;
	}
	
	
	for (int i = 1; i <= N; ++ i)
	{
		int nod = H[1];
		
		cont[nod] = true;
		
		swap (H[1], H[dim]);
		swap (poz[H[1]], poz[H[dim]]);
		
		-- dim;
		pop (1);
		
		for (unsigned int t = 0; t < lista[nod].size(); ++ t)
		{
			int node = lista[nod][t].first;
			
			if (cont[node]) continue;
			
			if (cost[node] > cost[nod] + lista[nod][t].second)
			{
				cost[node] = cost[nod] + lista[nod][t].second;
				
				int poz_h = poz[node];
				
				if (poz_h / 2 >= 1 && cost[H[poz_h]] > cost[H[poz_h / 2]]) pop (poz_h);
				else push (poz_h);
			}
		}
	}
	
	
	for (int i = 2; i <= N; ++ i)
		if (cost[i] != inf) g << cost[i] << " ";
		else g << 0 << " ";
	
	
	return 0;
}