#include<stdio.h>
#include<stdlib.h>

#define inf 666031

typedef struct nod{
	int info;
	int cost;
	struct nod *next;
}nod;

typedef struct{
	int vf;
	int dist;
	int pred;
}triplet;

nod *a[1000009];

void swap(int *a,int *b){
	int t;
	t = *a;
	*a = *b;
	*b = t;
}

void urca(int poz,triplet *h){
	int t = poz / 2;
	while(t >= 1){
		if(h[t].dist <= h[poz].dist)
			break;
		swap(&h[t].vf,&h[poz].vf);
		swap(&h[t].dist,&h[poz].dist);
		swap(&h[t].pred,&h[poz].pred);
		poz = t;
		t = poz / 2;
	}
}

void coboara(int poz,int n,triplet *h){
	int fs = 2 * poz,fd = 2 * poz + 1,pmin = poz;
	if(fs <= n && h[fs].dist < h[pmin].dist)
		pmin = fs;
	if(fd <= n && h[fd].dist < h[pmin].dist)
		pmin = fd;
	if(pmin != poz){
		swap(&h[poz].vf,&h[pmin].vf);
		swap(&h[poz].dist,&h[pmin].dist);
		swap(&h[poz].pred,&h[pmin].pred);
		coboara(pmin,n,h);
	}
}

void afis_stiva(nod *u){
	while(u != NULL){
		printf("%d %d ; ",u->info,u->cost);
		u = u->next;
	}
}

void adauga(int x,nod **u,int c){
	nod *nou = (nod*)malloc(sizeof(nod));
	nod *ultim = *u;
	nou->info = x;
	nou->cost = c;
	nou->next = ultim;
	*u = nou;
}

void dijkstra(int x,int n){
	FILE *g = fopen("dijkstra.out","w");
	nod *u;
	int i,l = 0;
	triplet *h = (triplet*)malloc((n + 1) * sizeof(triplet));
	int *d = (int*)malloc((n + 1) * sizeof(int));
	//int *m = (int*)malloc((n + 1) * sizeof(int));
	for(i = 1;i <= n;i++)
		d[i] = inf;
	int vf = x;
	d[vf] = 0; 
	for(u = a[vf];u != NULL;u = u->next){
		h[++l] = (triplet){u->info,d[vf] + u->cost,vf};
		//d[u->info] = d[vf] + u->cost;
		urca(l,h);
	}
	while(1){
		while(l != 0 && d[h[1].vf] != inf){
			swap(&h[1].vf,&h[l].vf);
			swap(&h[1].dist,&h[l].dist);
			swap(&h[1].pred,&h[l--].pred);
			coboara(1,l,h);
		}
		if(l==0)
			break;
		vf = h[1].vf;
		d[vf] = h[1].dist;
		for(u = a[vf];u != NULL;u=u->next)
		{
			h[++l] = (triplet){u->info,d[vf] + u->cost,vf};
			urca(l,h);
		}
	}
	for(i = 2;i <= n;i++)
		if(d[i] == inf)
			fprintf(g,"0 ");
		else
			fprintf(g,"%d ",d[i]);
	fclose(g);
}

int main(){
	FILE *f;
	f = fopen("dijkstra.in","r");
	int i,n,m,k1,k2,c;
	fscanf(f,"%d%d",&n,&m);
	for(i = 1;i <= n;i++)
		a[i] = NULL;
	for(i = 0;i < m;i++){
		fscanf(f,"%d%d%d",&k1,&k2,&c);
		adauga(k2,&a[k1],c);
	}
	/*for(i = 1;i <= n;i++){
		afis_stiva(a[i]);
		printf("\n");
	}*/
	dijkstra(1,n);
	fclose(f);
	return 0;
}