#include <stdio.h>
#include <iostream>
using namespace std;
#define INF 1 << 30
const int maxn = 50001;

int n,heapsize,a[maxn],dist[maxn],poz[maxn],cont = 2,m;
void Dijkstra(int);
struct graf
{
int nod, cost;
graf *next;
};
 
graf *A[maxn];


void add(int where, int what, int cost)
{
graf *q = new graf;
q->nod = what;
q->cost = cost;
q->next = A[where];
A[where] = q;
}
 
void read()
{
	scanf( "%d %d", &n, &m);
 
	int x, y, z;
	for ( int i = 1; i <= m; ++i )
	{
		scanf( "%d %d %d", &x, &y, &z);
		add(x, y, z);
	}
}
int main(){
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	read();
	Dijkstra(1);
	for(int i = 2; i <= n; ++i)
		printf( "%d ", dist[i] == INF ? 0 : dist[i]);
	return 0;
}
void min_heapify(int i){
	int l = 2 * i,r = 2 * i + 1,largest;
	if(l <= heapsize && a[l] < a[i])
		largest = l;
	else
		largest = i;
	if(r <= heapsize && a[r] < a[largest])
		largest = r;
	if(largest != i){
		int aux = a[largest],aux1 = poz[largest];
		a[largest] = a[i];
		poz[largest] = poz[i];		//acelasi lucru pentru poz ca si pt a[] .. se face swap intre elemente;
		a[i] = aux;
		poz[i] = aux1;				//acelasi lucru pentru poz ca si pt a[] .. se face swap intre elemente;
		min_heapify(largest);
	}
}
void heap_decrease_key(int i, int key){
	if(key > a[i])
		return;
	a[i] = key;
	while(i > 1 && a[i / 2] > a[i]){
		int aux = a[i],aux1 = poz[i];
		a[i] = a[i/2];
		poz[i] = poz[i/2];
		a[i/2] = aux;
		poz[i/2] = aux1;
		i >>= 1;
	}
}
void min_heap_insert(int key){
	heapsize++;
	a[heapsize] = INF;
	heap_decrease_key(heapsize,key);
}
int heap_extract_min(){
	if(heapsize < 1)
		return 0;
	int m1 = poz[1];
	a[1] = a[heapsize];
	poz[1] = poz[heapsize];
	heapsize--;
	min_heapify(1);
	return m1;
}
void Dijkstra(int x){
	int u;
	poz[1] = 1;
	for(int i = 2; i <= n; ++i){
		dist[i] = INF;
	}
	dist[1] = 0;	//a[] este un min priority queue
	min_heap_insert(dist[1]);
	while(heapsize || cont > 1){			//Main loop while queue is not empty
		u = heap_extract_min();
		if(dist[u] == INF || u == 0)
			break;
		--cont;
		graf *q = A[u];
		while(q){
			int alt = dist[u] + q->cost;
			if(q->nod != u)
			if(alt < dist[q->nod]) {
				dist[q->nod] = alt;	//in loc de q->nod, index i pt matrice
				poz[cont++] = q->nod;
				min_heap_insert(dist[q->nod]);
			}
			q = q->next;
		}
	}
}