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

ifstream fin("djikstra.in");
ofstream fout("djikstra.out");

#define DMAX 100001
#define INF  250000001

int n, m, s;

struct Graf{
	int d[DMAX];
	vector<int> Adj[DMAX], W[DMAX];
} G;

struct Heap{
	int size;
	int * d[DMAX], ind[DMAX];
} Q;

void MinHeapify(int i){
	int smalest = i;
	if ((2 * i + 1) < Q.size && *(Q.d[i]) > *(Q.d[2 * i + 1]))
		smalest = 2 * i + 1;
	if ((2 * i + 2) < Q.size && *Q.d[smalest] > *Q.d[2 * i + 2]){
		smalest = 2 * i + 2;
	}

	if (smalest != i){
		swap(Q.d[i], Q.d[smalest]);
		swap(Q.ind[i], Q.ind[smalest]);
		MinHeapify(smalest);
	}
}

int ExtractMin(){
	swap(Q.d[1], Q.d[Q.size]);
	swap(Q.ind[1], Q.ind[Q.size]);
	return Q.ind[Q.size--];
}


void Relax(int u, int v, int w){
	if (G.d[v] > G.d[u] + w){
		G.d[v] = G.d[u] + w;
	}
}

void Djikstra(int root){
	int i, next, lg;

	Q.size = n;
	for (i = 1; i <= n; i++){
		Q.d[i] = &G.d[i];
		Q.ind[i] = i;
	}

	G.d[root] = 0;
	while (Q.size){
		MinHeapify(1);
		next = ExtractMin();

		lg = G.Adj[next].size();
		for (i = 0; i < lg; i++){
			Relax(next, G.Adj[next][i], G.W[next][i]);
		}
	}
}

int main(){
	int i, x, y, w;

	fin >> n >> m;
	for (i = 0; i < m; i++){
		fin >> x >> y >> w;
		G.Adj[x].push_back(y);
		G.W[x].push_back(w);
		G.d[x] = INF;
	}

	Djikstra(1);

	for (i = 2; i <= n; i++)
		if (G.d[i] == INF)	fout << 0 << ' ';
		else	fout << G.d[i] << ' ';

	return 0;
}