#include <stdio.h>

#define NMAX 50005
#define INF 1 << 30

int N, M, nh;
int d[NMAX], h[NMAX], poz[NMAX];

struct nod
{
	int v, cost;
	nod *next;
};

nod *m[NMAX];


void adaug(int a, int b, int c)
{
	nod *aux;
	aux = new nod;
	aux -> v = b;
	aux -> cost = c;
	aux -> next = m[a];
	m[a] = aux;
}


void swap(int i, int j)
{
	int aux;
	aux = h[i];
	h[i] = h[j];
	h[j] = aux;
	
}

void HeapUp(int k)
{
	int t;
	if ( k <= 1) return;
	t = k >> 1;
	if ( d[h[t]] > d[h[k]])
	{
        poz[h[t]] = k;
        poz[h[k]] = t; 
		swap(t, k);
		HeapUp(t);
	}
}


void HeapDw(int k)
{
    int i;
    i = k << 1;
    if ( i <= nh )
    {
       if ( (i | 1) <= nh &&  d[h[( i | 1 )]] < d[h[i]] )
          i++;
       if ( d[h[k]] > d[h[i]])
       {
          poz[h[k]] = i;
          poz[h[i]] = k;
          swap(i, k);
          HeapDw(i);
       }    
    }
}


int main()
{
	int i, a, b, c, min, aux;
	nod *p;
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	scanf("%d %d", &N, &M);
	for ( i = 1; i <= M; i++)
	{
		scanf("%d %d %d", &a, &b, &c);
		adaug(a, b, c);
	}

	for ( i = 2; i <= N; i++)
	{
		d[i] = INF;
		poz[i] = -1;
	}

	h[1] = 1;
	poz[1] = 1;
	nh = 1;

	while ( nh )
	{
		min = h[1];
        swap(1, nh);
	    poz[h[1]] = 1;
        	
		nh--;
		HeapDw(1);

    	for ( p = m[min]; p; p = p -> next)
			if ( d[ p -> v] > d[min] + p -> cost)
			{
				d[ p -> v] = d[min] + p -> cost;
				if ( poz[p->v] == -1)
				{
					nh++;
					h[nh] = p -> v;
					poz[p-> v] = nh;
				}
				HeapUp( poz[p->v] );
			}
	}

	for ( i = 2; i <= N; i++)
		printf("%d ", d[i] == INF ? 0 : d[i]);



	return 0;
}