#include <fstream>
#include <cstring>
using namespace std;

const unsigned int MAXN = 50001, INF=0xeeeeeeee;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

inline unsigned int PARENT (unsigned int idx) { return (idx-1)>>1; }
inline unsigned int LEFT (unsigned int idx) { return (idx<<1)+1; }
inline unsigned int RIGHT (unsigned int idx) { return (idx+1)<<1; }
inline void SWAP (unsigned int &x, unsigned int &y) { unsigned int z=x; x=y; y=z; }

struct Nod {
	unsigned int dest,cost;
	Nod *n;
};
Nod *graf[MAXN];
unsigned int dist[MAXN], inheap[MAXN], heap[MAXN], heapsize;
void heap_push (unsigned int idx)
{
	if (inheap[idx]) return;
	inheap[idx] = 1;
	unsigned int crt = heapsize++;
	while (crt > 0) {
		if (dist[idx] < dist[ heap[PARENT(crt)] ]) {
			heap[crt] = heap[PARENT(crt)];
			crt = PARENT(crt);
		}
		else break;
	}
	inheap[idx] = 1;
	heap[crt] = idx;
}
unsigned int heap_pop () {
	unsigned int ret = heap[0];
	heap[0] = heap[--heapsize];
	//heapify(0):
	unsigned int crt=0;
	while (LEFT(crt) < heapsize) {
		unsigned int min=dist[heap[crt]],minv=crt;
		if (dist[ heap[LEFT(crt)] ] < min) { min = dist[ heap[LEFT(crt)] ]; minv = LEFT(crt); }
		if (RIGHT(crt) < heapsize && dist[ heap[RIGHT(crt)] ] < min) { min = dist[ heap[RIGHT(crt)] ]; minv=RIGHT(crt); }
		if (minv != crt) {
			SWAP(heap[crt],heap[minv]);
			crt = minv;
		}
		else break;
	}
	return ret;
}

int main ()
{
	unsigned int N,M,i;
	in >> N >> M;
	for (i=0; i<M; ++i) {
		unsigned int src;
		Nod *n = new Nod;
		in >> src >> n->dest >> n->cost;
		n->n = graf[src];
		graf[src] = n;
	}
	
	for (i=1; i<=N; ++i) {
		dist[i] = INF;
		inheap[i] = 0;
	}
	dist[1] = 0;
	heap_push(1);
	
	while (heapsize) {
		unsigned int src = heap_pop();
		for (Nod *nod = graf[src]; nod; nod=nod->n) {
			if (dist[nod->dest] > dist[src]+nod->cost) {
				//relax
				dist[nod->dest] = dist[src]+nod->cost;
				heap_push(nod->dest);
			}
		}
	}
	for (unsigned int i=2; i<=N; ++i) out << ((dist[i]==INF)?0:dist[i]) << ' ';
	out << '\n';
	return 0;
}