#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];
int i, j, c, N, M, poz, pas, minim;

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;
	
	for (pas=1;pas<=N;pas++) {
		minim = INF;
		for (i=1;i<=N;i++)
			if (V[i] == 0 && D[i] < minim) {
				minim = D[i];
				poz = i;
			}
		if (minim == INF)
			break;
		V[poz] = 1;
		
		for (i = 0; i<L[poz].size(); i++) {
//			g<<it->second;
			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;
		}
	}
	
	for (i=2;i<=N;i++)
		if (D[i] == INF)
			g<<"0 ";
		else
			g<<D[i]<<" ";
	
	return 0;
}