#include<fstream>
#include<cstdio>
#include<vector>

#define pb push_back
#define mp make_pair
#define T ((i)/2)
#define LS ((i)*2)
#define RS ((i)*2+1)

using namespace std;

const int MaxN = 50001;
const int Inf = 0x3f3f3f3f;

const char InFile[] = "dijkstra.in";
const char OutFile[] = "dijkstra.out";

int n,m,nh,d[MaxN],poz[MaxN],heap[MaxN];
vector< pair<int,int> > G[MaxN];

void upheap(int i)
{
	if( i > 1 )
		if( d[heap[i]] < d[heap[T]] )
			{
				swap(heap[i],heap[T]);
				swap(poz[heap[i]],poz[heap[T]]);
				upheap(T);
			}
}

void downheap(int i)
{
	int m;
	m = i;
	if( LS <= nh && d[heap[m]] > d[heap[LS]] )
		m = LS;
	if( RS <= nh && d[heap[m]] > d[heap[RS]] )
		m = RS;
	if( m != i )
		{
			swap(heap[i],heap[m]);
			swap(poz[heap[m]],poz[heap[i]]);
			downheap(m);
		}
}

void dijkstra()
{
	int i,nod;
	vector< pair<int,int> >::iterator it,iend;
	for( i = 0 ; i < MaxN ; i++ )
		{
			d[i] = Inf;
			poz[i] = heap[i] = i;
		}
	d[1] = 0;
	nh = n;
	while( nh )
		{
			nod = heap[1];
			swap(heap[1],heap[nh]);
			swap(poz[heap[1]],poz[heap[nh]]);
			--nh;
			downheap(poz[heap[1]]);
			iend = G[nod].end();
			for( it = G[nod].begin() ; it < iend ; ++it )
				if( d[it -> first] > d[nod] + it -> second )
					{
						d[ it -> first ] = d[nod] + it->second;
						upheap(poz[it->first]);
					}
		}
}

int main()
{
	freopen( InFile , "r" , stdin );
	freopen( OutFile , "w" , stdout );
	int i,a,b,c;
	scanf("%d%d" , &n , &m );
	for( i = 0 ; i < m ; i++ )
		{
			scanf("%d%d%d" , &a , &b , &c);
			G[a].pb(mp(b,c));
		}
	dijkstra();
	for( i = 2 ; i <= n ; i++ )
		printf("%d " , d[i] < Inf ? d[i] : 0 );
	printf("\n");
	return 0;
}