#include<stdio.h>
#include<string.h>

#define MAXN 50001
#define inf 2000000000

struct nod
{
	int val, nr;
	nod *urm;
};

int d[MAXN], poz[MAXN], t[MAXN], h[MAXN], n, m, k;
nod *v[MAXN];

void swap(int a, int b)
{
	int aux;
	aux = h[a];
	h[a] = h[b];
	h[b] = aux;
}

int tata(int k)
{return k/2;}

int fiu_st(int k)
{return 2*k;}

int fiu_dr(int k)
{return 2*k+1;}

void urca(int x)
{
   while(x>1 && d[h[tata(x)]] > d[h[x]])
   {
       poz[h[x]] = tata(x);
       poz[h[tata(x)]] = x;
       swap(x, tata(x));
       x=tata(x);
   }
}

void coboara(int x)
{
	int fiu;
    while(2*x<=k)
    {
		fiu=fiu_st(x);
		if(fiu_dr(x)<=k && d[h[fiu]] > d[h[fiu_dr(x)]]) fiu = fiu_dr(x);
		if(d[h[x]] < d[h[fiu]]) return;
		poz[h[x]] = fiu;
        poz[h[fiu]] = x;
        swap(x, fiu);
		x=fiu;
    }
}

void adauga(int a, int b, int c)
{
	nod *p;
	p = new nod;
	p->nr = b;
	p->val = c;
	p->urm = v[a];
	v[a] = p;
}

void dijkstra(int x)
{
	int min, i;
    nod *p;
	for(i=1; i<=n; i++)
    {
        d[i] = inf;
        poz[i] = h[i] = t[i] = 0;
    }
	k = 0;
    d[x] = 0;
	h[1] = x;
	k = 1;
	while(k)
	{
		min = h[1];
        swap(1, k);
        poz[h[1]] = 1;
		k--;
		coboara(1);
		p = v[min];
		while(p!=NULL)
		{
			if(d[p->nr] > d[min] + p->val)
			{
				d[p->nr] = d[min] + p->val;
				t[p->nr] = min;
				if(poz[p->nr]==0)
				{
					h[++k] = p->nr;
					poz[p->nr] = k;
					urca(k);
				}
				else	urca(poz[p->nr]);
			}
			p = p->urm;
		}
	}
}

int main()
{
	freopen("dijkstra.in", "rt", stdin);
	freopen("dijkstra.out", "wt", stdout);
	scanf("%i %i", &n, &m);
	int i, a, b, c;
	for(i=1; i<=m; i++)
	{
		scanf("%i %i %i", &a, &b, &c);
		adauga(a, b, c);
	}
	dijkstra(1);
	for(i=2; i<=n; i++)		
        if(d[i]!=inf) printf("%i ", d[i]);
        else printf("0 ");
	return 0;
}