#include <cstdio>
#include <vector>
//#include <utility>
//#include <functional>

using namespace std;

#define INF UINT_MAX

#define MAXNODURI 50000

int main (void)
{
	unsigned int nrNoduri, nrArcuri;
	typedef vector<pair<unsigned int, unsigned int> > G;
	G graf[MAXNODURI];
	unsigned int stack[MAXNODURI], *stack_push, dist[MAXNODURI];
	
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	
	scanf("%u %u\n", &nrNoduri, &nrArcuri);
	
	for (unsigned int i=0; i<nrNoduri; ++i)
		dist[i] = INF;
	
	for (unsigned int i=0; i<nrArcuri; ++i) {
		unsigned int src, dest, cost;
		scanf("%u %u %u\n", &src, &dest, &cost);
		--src; --dest;
		graf[src].push_back( make_pair(dest, cost) );
	}
	
	stack_push = stack;
	
	*(++stack_push) = 0;
	dist[0] = 0;
	/* stack not empty */
	while (stack_push > stack) {
		unsigned int src = *(--stack_push), v;
		for (G::const_iterator iter = graf[src].begin(); iter != graf[src].end(); ++iter)
			if ( (v= dist[src] + iter->second) < dist[iter->first]) {
				dist[iter->first] = v;
				*(stack_push++) = iter->first;
			}
	}
	for (unsigned int i=1; i<nrNoduri; ++i)
		printf("%u ", dist[i]==INF?0:dist[i]);
	printf("\n");
	return 0;
}