#include <fstream>
using namespace std;

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

const unsigned int MAXN = 50001;
const unsigned int INF = 0xEEEEEEEE;
unsigned int dist[MAXN],heappos[MAXN],heap[MAXN],heapsize=0;
char visited[MAXN];

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)+2; }
inline void SWAP (unsigned int &x, unsigned int &y) { unsigned int aux=x; x=y; y=aux; }

inline void heapify (unsigned int idx)
{
	while (LEFT(idx) < heapsize) {
		unsigned int min=dist[heap[idx]], minidx=idx;
		if (dist[heap[LEFT(idx)]] < min) { min = dist[heap[LEFT(idx)]]; minidx=LEFT(idx); }
		if (RIGHT(idx) < heapsize && dist[heap[RIGHT(idx)]]<min) { min=dist[heap[RIGHT(idx)]]; minidx=RIGHT(idx); }
		if (idx != minidx) {
			SWAP(heap[idx], heap[minidx]);
			heappos[heap[idx]] = idx;
			heappos[heap[minidx]] = minidx;
			idx=minidx;
		} else break;
	}
}

inline void heap_push (unsigned int idx)
{
	unsigned int pos;
	if (heappos[idx] == INF) pos=heapsize++;
	else pos = heappos[idx];
	while (pos > 0) {
		if (dist[idx] < dist[heap[PARENT(pos)]]) {
			heap[pos] = heap[PARENT(pos)];
			heappos[heap[PARENT(pos)]] = pos;
			pos = PARENT(pos);
		} else break;
	}
	heappos[idx] = pos;
	heap[pos] = idx;
}

inline unsigned int heap_pop ()
{
	unsigned int ret = heap[0];
	heap[0] = heap[--heapsize];
	heappos[ret] = INF;
	heappos[heap[0]] = 0;
	heapify(0);
	return ret;
}


struct Nod {
	unsigned int dest, cost;
	Nod *n;
};

Nod *graf[MAXN];

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