#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define maxN 500005
#define INF 0x3f3f3f3f

int cost[maxN] , N , M , nod;
int pozH[maxN] , H[maxN] , dim;
bool viz[maxN];

vector < pair <int , int> > lista[maxN];

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


void pop (int nod)
{
	int f1 , f2 , nodmin = nod;
	
	f1 = nod * 2;
	f2 = nod * 2 + 1;
	
	if (f1 <= dim && cost[H[f1]] < cost[H[nodmin]])
		nodmin = f1;
	
	if (f2 <= dim && cost[H[f2]] < cost[H[nodmin]])
		nodmin = f2;
	
	if (nod == nodmin)
		return;
	
	swap (H[nodmin] , H[nod]);
	swap (pozH[H[nodmin]] , pozH[H[nod]]);
	
	pop (pozH[H[nodmin]]);

}


void get_min ()
{
	nod = H[1];
	
	viz[nod] = true;
	
	swap (H[1] , H[dim]);
	swap (pozH[H[1]] , pozH[H[dim]]);
	
	--dim;
	
	pop (pozH[H[1]]);
}


int main ()
{
	freopen ("dijkstra.in" , "r" , stdin);
	freopen ("dijkstra.out" , "w" , stdout);
	
	scanf ("%d %d" , &N , &M);
	
	for (int i = 1 ; i <= N ; ++i)
		cost[i] = INF;
	
	cost[1] = 0;
	
	for (int i = 1 ; i <= N ; ++i)
	{
		pozH[i] = ++dim;
		H[dim] = i;
		
		push (pozH[i]);
	}
	
	int a , b , c;
	
	for (int i = 1 ; i <= M ; ++i)
	{
		scanf ("%d %d %d" , &a , &b , &c);
		
		lista[a]. push_back (make_pair (b , c));
	}
	
	int nodcur , costmuc;
	
	while (dim)
	{
		get_min ();
		
		for (unsigned i = 0 ; i < lista[nod].size () ; ++i)
		{
			nodcur = lista[nod][i].first;
			costmuc = lista[nod][i].second;
			
			if (viz[nodcur]) continue;
			
			if (cost[nod] + costmuc < cost[nodcur])
			{
				cost[nodcur] = cost[nod] + costmuc;
				
				push (pozH[nodcur]);
			}
		}
	}
	
	for (int i = 2 ; i <= N ; ++i)
	{
		if (cost[i] == INF)
		{
			printf ("0 ");
			continue;
		}
		
		printf ("%d " , cost[i]);
	}
	
	return 0;
}