#include <iostream>
#include <fstream>
#include <set>
#include <vector>

#define MAXN 50010
#define MAXM 250100
#define INF 1000000000

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int N,M;
struct Edge {
	int at;
	int cost;
};
struct Node {
	int dist;
	vector<Edge> Adj;
};
Node V[MAXN];

int H[MAXN];
bool inHeap[MAXN];

void siftUp(int x) {
	while (x/2 && V[H[x]].dist < V[H[x/2]].dist) {
		swap(H[x],H[x/2]);
		x >>= 2;
	}
}

void siftDown(int x) {
	int left,right,minInd;
	left = x * 2;
	right = x * 2 + 1;
	if (left > H[0]) return;
	minInd = left;
	if (right <= H[0]) {
		if (V[H[minInd]].dist < V[H[right]].dist) {
			minInd = right;
		}
	}
	swap(H[x],H[minInd]);
	siftDown(minInd);
}

int removeTop() {
	if (H[0] == 0) return -1;
	else H[1] = H[H[0]];
	H[0]--;
	siftDown(1);
}

void read_f() {
	int i,x,y,c;
	Edge tmp;
	fin >> N >> M;
	for (i=0;i<M;++i) {
		fin >> x >> y >> c;
		x -= 1;
		y -= 1;
		tmp.at = y;
		tmp.cost = c;
		V[x].Adj.push_back(tmp);
	}
	for (i=0;i<N;++i) V[i].dist = INF;
	memset(inHeap,0,sizeof(inHeap));
	V[0].dist = 0;
	H[++H[0]] = 0;
	inHeap[0] = 1;
	fin.close();
}

void dijktra() {
	int x,i;
	while (H[0] > 0) {
		x = H[1];
		removeTop();	
		inHeap[x] = 0;
		for (i=0;i<V[x].Adj.size();++i) {
			if (V[V[x].Adj[i].at].dist > V[x].dist + V[x].Adj[i].cost) {	
				V[V[x].Adj[i].at].dist = V[x].dist + V[x].Adj[i].cost;
				if (!inHeap[V[x].Adj[i].at]) {
					inHeap[V[x].Adj[i].at] = 1;
					H[++H[0]] = V[x].Adj[i].at;
					siftUp(H[0]);
				}
			}
		}
	}
}

void write_f() {
	int i;
	for (i=1;i<N;++i)
		fout << ((V[i].dist >= INF)?0:V[i].dist) << " ";
	fout << "\n";
	fout.close();
}

int main() {
	read_f();
	dijktra();
	write_f();
	return 0;
}