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

using namespace std;

#define N 50100
#define mp make_pair
#define pb push_back/*
#define ls(k) k<<1
#define rs(k) (k<<1)+1
#define father(k) k>>1*/
#define F first
#define S second
#define INF 0x3f3f3f3f

inline int ls(int k){return k<<1;}
inline int rs(int k){return (k<<1)+1;}
inline int father(int k){return k>>1;}

vector< pair< int, int > > a[N];
int n, m, k,
	d[N], h[N], poz[N];


void citire(){
int i, x, y, z;
	scanf("%d %d", &n, &m);
	for (i = 1; i <= m; ++i){
		scanf("%d %d %d", &x, &y, &z);
		a[x].pb(mp(y,z));
	}
}

void upheap(int w){
	while (w > 1){
		if ( d[ h[father(w)] ] > d[ h[w] ] )
		{
			swap(poz[ h[w] ], poz[ h[father(w)] ]);
			swap(h[w], h[father(w)] );
			
			w = father(w);			
		}
		else
			w = 1; 
	}
}

void downheap(int w){
int son;
	while (w <= k){
		son = 0;
		 if (ls(w) <= k){
			son = ls(w); 
			if (rs(w) <= k)
				if (d[ h[ rs(w) ] ] < d[ h[ ls(w) ] ])
					son = rs(w);
		 } 
		 else
			 return;
		 
		 if (d[ h[w] ] > d[ h[ son ] ])
		 {
			 swap(poz[h[w]], poz[h[son]]);
			 swap(h[w], h[son]);
			 w = son;
		 }
		 else
			 return;
	}
}



void dijkstra_heap(){
int i, cost2, nod2;

	for (int i = 2; i <= n; ++i)
		d[i] = INF, poz[i] = -1;
	
	poz[1] = 1; h[++k] = 1;

	while (k){
		int min = h[1];
		swap(h[1], h[k]);
		poz[h[1]] = 1;
		--k;
		downheap(1);
		
		for (i = 0; i < a[min].size(); i++){
			
			nod2 = a[min][i].F; cost2 = a[min][i].S;
			
			if (d[nod2] > d[min] + cost2)
			{
				d[nod2] = d[min] + cost2;
				
				if (poz[nod2] != -1)
					upheap(poz[nod2]);
				else{
					h[++k] = nod2;
					poz[ h[k] ] = k;
					upheap(k);
				}
			}
		}
	}
}


int main(){
int i;
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	
	citire();
	dijkstra_heap();
	
	for (i = 2; i <= n; ++i)
		printf("%d ", (d[i] == INF ? 0 : d[i]) );
	printf("\n");
	
	return 0;
}