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

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


int N, M;

list *listad[50001];
int viz[50001], dist[50001];
priority_queue <pair<int, int>, vector< pair<int, int> >, greater<pair<int, int> > > heap;


int selectHeapNode() {
	pair<int, int> aux;
	aux = heap.top();
	heap.pop();
	return aux.first;
}

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

	for (int i = 1; i < N; i++) {
		y = selectHeapNode();
		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;
				heap.push(make_pair(aux->neigh, dist[aux->neigh]));
			}
			aux = aux->next;
		}
	}
	
}

int main() {

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

	scanf("%d %d", &N, &M);
	
	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;
			heap.push(make_pair(y,c));
		}
	}

	dijkstra();

	for (i = 2; i <= N; i++)
		if (dist[i]!=INT_MAX) printf("%d ",dist[i]);
		else printf("0 ");
	printf("\n");

	return 0;
}