#include<cstdio>
#include<climits>
using namespace std;


struct list {
	int neigh;
	int cost;
	list *next;
};

int N, M;

list **listad;
int *viz, *dist;


int selectNode() {
	int min = INT_MAX;
	int poz = -1;

	for (int i = 2; i <= N; i++){
		if (!viz[i] && dist[i] < min) {
			min = dist[i];
			poz = i;
		}	
	}

	return poz;
}
void dijkstra() {
	viz[1] = 1;
	list *aux;
	int y;

	for (int i = 1; i < N; i++) {
		y = selectNode();
		viz[y] = 1;
		aux = listad[y];

		while(aux) {
			if (!viz[aux->neigh] && dist[aux->neigh] > dist[y] + aux->cost) {
				dist[aux->neigh] = dist[y] + aux->cost;
			}
			aux = aux->next;
		}
	}
	
}

int main() {

	freopen ("dijkstra.in", "r", stdin);
	freopen ("dijkstra.out", "w", stdout);

	scanf("%d %d", &N, &M);
	
	listad	= new list*[N+1];
	viz		= new int[N+1];
	dist	= new int[N+1];

	int x, y, c, i;

	for (i = 1; i <= N; i++) {
		listad[i] = NULL;
		viz[i] = 0;
		dist[i] = INT_MAX;
	}

	for (i = 0; i < M; i++) {
		scanf("%d %d %d", &x, &y, &c);
		list *aux = new list;
		aux->cost = c;
		aux->neigh = y;
		if (listad[x]) {
			aux->next = listad[x];			
			listad[x] = aux;
		}
		else { 
			aux->next = NULL;
			listad[x] = aux;
		}

		if (x == 1) dist[y] = c;
	}

	dijkstra();
	for (i = 2; i <= N; i++)
		printf("%d ",dist[i]);
	printf("\n");

	delete []listad;

	return 0;
}