#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 MAX = 50010;
vector< pr > G[MAX];
long D[MAX];
long n,m;

// 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]]);
	}

	for (long x=start; ;) {
		long fs = 0x3f3f3f3f, fd = 0x3f3f3f3f;
		if ( 2*x+1 < lh )		// am fiu stanga
			fs = D[ Heap[2*x+1] ];
		if ( 2*x+2 < lh )		// am fiu dreapta
			fd = D[ Heap[2*x+2] ];
		if ( D[Heap[x]] < min(fs, 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]] );
		} else {				// ghici
			swap( Heap[x], Heap[2*x+2]);
			swap( pos[Heap[x]], pos[Heap[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 stivei
	long r = Heap[0];
	swap( Heap[0], Heap[lh-1] );
	swap( pos[Heap[0]], pos[Heap[lh-1]] );

	--lh;
	heap_update(0);
	return r;
}


void dijkstra(long s) {
	memset(D, 0x3f, sizeof(D));
	D[s] = 0; //U[s] = 1;
	heap_push(s);
	while ( lh>0 ) {
		long x = heap_pop();
//		if ( U[x] ) 
//			continue;
		long n = 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;
				heap_push(G[x][i].x);
//				U[G[x][i].x] = 1;
			}
//		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]);
	printf("\n");
	return 0;
}