#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

struct pr {
	long x, c;
	pr(long a, long b) { x = a; c = b; }
};

const long inf = 0x3f3f3f3f;
const long MAX = 50100;
vector< pr > G[MAX];
long D[MAX];
long n,m;
bool U[MAX];

// pt heap
long lh, Heap[MAX];
long pos[MAX];

void heap_update(long start) {	// pune un elem in heap pe poz corespunzatoare
	for (long x=start; x>0 && D[ Heap[x] ] < D[ Heap[(x-1)/2] ]; x=(x-1)/2) {
		swap(Heap[x], Heap[(x-1)/2]);
//		swap(pos[Heap[x]], pos[Heap[(x-1)/2]]);
		pos[Heap[x]] = x; pos[Heap[(x-1)/2]] = (x-1)/2;
	}
	if ( start )
		return;

	for (long x=start; x<lh;) {
		long fs = inf, fd = inf;
		if ( 2*x+1 < lh )		// am fiu stanga
			fs = D[ Heap[2*x+1] ];
		else
			break;
		if ( 2*x+2 < lh )		// am fiu dreapta
			fd = D[ Heap[2*x+2] ];
		if ( D[Heap[x]] < fs && D[Heap[x]] < fd )	// l-am adancit destul
			break;
		if ( fs < fd ) {		// il ducem in stanga
			swap( Heap[x], Heap[2*x+1]);
			swap( pos[Heap[x]], pos[Heap[2*x+1]] );
			x = 2*x+1;
		} else {				// ghici
			swap( Heap[x], Heap[2*x+2]);
			swap( pos[Heap[x]], pos[Heap[2*x+2]] );
			x = 2*x+2;
		}
	}
}

void heap_push(long p) {		// baga un elem in heap
	Heap[lh++] = p;
	pos[p] = lh-1;
	heap_update(lh-1);
}

long heap_pop() {				// scoate varful heapului
	long r = Heap[0];
	swap( Heap[0], Heap[lh-1] );
	swap( pos[Heap[0]], pos[Heap[lh-1]] );

	Heap[--lh]=0;
	if ( lh )
		heap_update(0);
	return r;
}


void dijkstra(long s) {
	memset(D, 0x3f, sizeof(D));
	D[s] = 0; U[s] = 1; pos[s] = 0;
	heap_push(s);
	while ( lh>0 ) {
		long x = heap_pop();
//		printf("Vizitam %ld %ld\n", x, D[x]);
		long n = (long)G[x].size();		// nr de vecini
		for (long i=0; i<n; ++i) 
			if ( D[G[x][i].x] > D[x]+G[x][i].c ) {
				D[G[x][i].x] = D[x] + G[x][i].c;
				if ( !U[G[x][i].x] ) {
					heap_push(G[x][i].x);
					U[G[x][i].x] = 1;
				} else 
					heap_update(pos[G[x][i].x]);
			}
//		U[x] = 0;
	}
}

int main() {
	freopen("dijkstra.in", "r", stdin);
	scanf("%ld %ld", &n, &m);
	while ( m-- ) {
		long x,y,c;
		scanf("%ld %ld %ld", &x, &y, &c);
		G[x].push_back( pr(y,c) );
	}

	dijkstra(1);

	freopen("dijkstra.out", "w", stdout);
	for (long i=2; i<=n; ++i)
		printf("%ld ", D[i]<inf ? D[i] : 0);
	printf("\n");
	return 0;
}