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

#define MAXN 50001
#define inf 2000000000

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

struct coada
{
	nod *a, *b;
	int nr;
};

int ExtrQ(coada *q)
{
	nod *p;
	int x;
	p = q->a;
	q->a = q->a->urm;
	x = p->val;
	q->nr--;
	if(q->nr==0) q->a = q->b = NULL;
	delete p;
	return x;
}

void IntrQ(coada *q, int x)
{
	nod *p;
	p = new nod;
	q->nr++;
	p->val = x;
	p->urm = NULL;
	if(q->b == NULL) q->a = q->b = p;
	else 
	{
		q->b->urm = p;
		q->b = p;
	}
}


int d[MAXN], poz[MAXN], t[MAXN], h[MAXN], s[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 bellman_ford(int x)
{
	int i, j, a, c;
	for(i=1; i<=n; i++) 
	{
		s[i] = 0;
		d[i] = inf;
	}
	d[x] = 0;
	s[x] = 1;
	coada *q;
	nod *p;
	q = new coada;	
	q->nr = 0;
	q->a = q->b = NULL;
	IntrQ(q, x);
	for(i=1; i<n && q->nr>0; i++)
	{
		c = q->nr;
		for(j=1; j<=c; j++)
		{
			a = ExtrQ(q);
			s[a] = 0;
			for(p = v[a]; p!=NULL; p=p->urm)
				if(d[p->nr] > d[a] + p->val)
				{
					d[p->nr] = d[a] + p->val;
					if(s[p->nr]==0) 
					{
						IntrQ(q, p->nr);
						s[p->nr] = 1;
					}
				}
		}
	}
	if(q->nr != 0) return 0;
	return 1;
}
			
		
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);
	}
	bellman_ford(1);
	for(i=2; i<=n; i++)		
        if(d[i]!=inf) printf("%i ", d[i]);
        else printf("0 ");
	return 0;
}