#include <fstream>
#include <vector>

#define INF 60000000
#define DIMN 50010

using namespace std;

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

vector<pair<int,int> > L[DIMN];

vector<pair<int,int> >::iterator it;

int V[DIMN], D[DIMN], H[DIMN], P[DIMN];
int i, j, c, N, M, poz, pas, minim, dH;

void up (int poz) {
	int c = poz;
	int p = c/2;
	int aux;
	while (p!=0) {
		if (D[H[c]] < D[H[p]]) {
			aux = H[c];
			H[c] = H[p];
			H[p] = aux;
			P[H[c]] = c;
			P[H[p]] = p;
			c = p;
			p = p/2;
		} else
			break;
	}
}

void down (int poz) {
	int p = poz;
	int c = 2*p;
	int aux;
	while (c <= dH) {
		if (c + 1 <= dH && D[H[c+1]] < D[H[c]])
			c++;
		if (D[H[p]] > D[H[c]]) {
			aux = H[p];
			H[p] = H[c];
			H[c] = aux;
			p = c;;
			c = p * 2;
		} else
			break;
	}
}


int main() {
	f>>N>>M;
	for (;M;M--) {
		f>>i>>j>>c;
		L[i].push_back(make_pair(j,c));
	}
	
	for (i=1;i<=N;i++) {
		D[i] = INF;
	}
	D[1] = 0;
	
	H[1] = 1;
	dH = 1;
	P[1] = 1;
	
	for (pas=1;pas<=N;pas++) {
		if (dH == 0) {
			break;
		}
		
		poz = H[1]; //nodul minim
		H[1] = H[dH];
		P[H[1]] = 1;
		dH--;
		down(1);
		
		for (i=0;i<L[poz].size();i++)
			if (V[ L[poz][i].first   ] == 0 && D[ L[poz][i].first  ] > D[poz] + L[poz][i].second) {
				D[ L[poz][i].first  ] = D[poz] + L[poz][i].second;
				if (P[L[poz][i].first] == 0) {
					dH++;
					H[dH] = L[poz][i].first;
					P[H[dH]] = dH;
					up(dH);
				} else {
					up(P[L[poz][i].first]);
					down(P[L[poz][i].first]);
				}
			}
	}
	
	for (i=2;i<=N;i++)
		if (D[i] == INF)
			g<<"0 ";
		else
			g<<D[i]<<" ";
	
	return 0;
}