#include <fstream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

int const NMAX = 100000;

int CM[NMAX];

int graph[NMAX][100], cost[NMAX][100];

inline bool dhcomp(int a, int b)
{
	return CM[a] > CM[b];
}

void dijkstra(int start)
{
	int dh[NMAX] = {}; // Dijkstra heap
	int dhL; // dhLength
	int cn, i, neigh;
	dh[0] = start;
	dhL = 1;
	CM[start] = 0;
	while(dhL) {
		cn = dh[0]; // curent node
		std::pop_heap(dh, dh + dhL--, dhcomp);
		for (i = 1; i <= graph[cn][0]; ++i) {
			neigh = graph[cn][i];
			if ( CM[neigh] == -1 ) { // if not processed
				CM[neigh] = CM[cn] + cost[cn][i];
				dh[dhL++] = neigh;
				std::push_heap(dh, dh + dhL, dhcomp);
			}
			else if (CM[cn] + cost[cn][i] < CM[neigh]) {
				CM[neigh] = CM[cn] + cost[cn][i];
				// note that here we traverse the whole heap
				// an optimization could be implemented in order to sort
				// only the branches CM[neigh] affects.
				std::make_heap(dh, dh + dhL, dhcomp);
			}
		}
	}
}

int main()
{
	int N, M, a, b, c, i;
	memset(CM, 0xFF, sizeof(int) * NMAX);
	freopen("dijkstra.out", "w", stdout);
	std::ifstream fin("dijkstra.in");
	fin >> N >> M;
	for (i = 0; i != M; ++i) {
		fin >> a >> b >> c;
		graph[a][++graph[a][0]] = b;
		cost [a][  graph[a][0]] = c;
	}
	dijkstra(3);
	for (i = 1; i <= N; ++i)
		if (CM[i] == -1) printf("0 ");
		else printf("%d ", CM[i]);
}