#include <stdio.h>

#define tata(x) (x>>1)
#define st(x) (x<<1)
#define dr(x) ((x<<1)|1)

#define INF 1000000000

#define N 50001
#define M 250001

int h[N]; //heap
int poz[N];
int d[N]; //distanta de la nodul 1 la celelalte noduri
int lh; //dimensiune (lungime) heap
int n,m; 

struct arc
{
	int x,y,c;
};

arc w[M];
int nrv[N];
int *la[N], *lc[N];

void init_d()
{
	for(int i = 2; i <= n; ++i) d[i] = INF;
	d[1] = 0;
}

inline void schimba(int ind_a, int ind_b)
{
	int aux = h[ind_a];
	h[ind_a] = h[ind_b];
	h[ind_b] = aux;
	
	poz[h[ind_a]] = ind_a;
	poz[h[ind_b]] = ind_b;
}

void coboara(int p)
{
	int id_max = p;
	if((st(p) <= lh) && (d[h[st(p)]] < d[h[id_max]])) id_max = st(p);
	if((dr(p) <= lh) && (d[h[dr(p)]] < d[h[id_max]])) id_max = dr(p);
	if(p != id_max)
	{
		schimba(p, id_max);
		coboara(id_max);
	}
}

void urca(int p)
{
	if(tata(p) && (d[h[tata(p)]] > d[h[p]])) 
	{
		schimba(tata(p), p);
		urca(tata(p));
	}
}

void citeste() //citeste din fisier
{
	char s[21];
	int x,y,c;
	freopen("dijkstra.in","r",stdin);
	scanf("%d %d\n",&n,&m);
	char *p;
	int i;
	for(i=1;i<=m;++i)
	{
		fgets(s,20,stdin);
		for(x=0,p=s;*p!=' ';++p)
			x=x*10+(*p-'0');
		++p;
		for(y=0;*p!=' ';++p)
			y=y*10+(*p-'0');
		++p;
		for(c=0;*p!='\n';++p)
			c=c*10+(*p-'0');
		w[i].x=x;
		nrv[x]++;
		w[i].y=y;
		w[i].c=c;
	}
	for(i=1;i<=n;++i) 
	{
		la[i]=new int[nrv[i] + 1];
		lc[i]=new int[nrv[i] + 1];
		la[i][0] = lc[i][0] = 0;
	}
	for(i=1;i<=m;++i)
	{
		la[w[i].x][++la[w[i].x][0]] = w[i].y;
		lc[w[i].x][++lc[w[i].x][0]] = w[i].c;
	}
	fclose(stdin);
}
void dijkstra()
{
	int x,y;
	lh = 1;
	h[1] = 1;
	poz[1] = 1;
	int i;
	while(lh)
	{
		x = h[1];
		schimba(1,lh);
		--lh;
		coboara(1);
		for(i = 1; i <= nrv[x]; ++i)
		{
			y = la[x][i];
			if(d[y] > d[x] + lc[x][i])
			{
				d[y] = d[x] + lc[x][i];
				h[++lh] = y;
				poz[y] = lh;
				urca(poz[y]);
			}				
		}
	}
}

void scrie()
{
	freopen("dijkstra.out","w",stdout);
	for(int i=2;i<=n;++i) printf("%d ", ((d[i]==INF)?(0):(d[i])));
	printf("\n");
	fclose(stdout);
}
int main()
{
	citeste();
	init_d();
	dijkstra();
	scrie();
	return 0;
}