#include <stdio.h>
const int maxn = 50001;
const int inf = 1 << 30;
//O(n^2 * log(n) ) 
struct graf
{
    int nod, cost;
    graf *next;
};

int max=0,n, m;
graf *a[maxn];
int d[maxn], h[maxn], poz[maxn], k;

void add(int where, int what, int cost)
{
    graf *q = new graf;
    q->nod = what;
    q->cost = cost;
    q->next = a[where];
    a[where] = q;
}

void read()
{
    freopen("dijkstra.in", "r",stdin);
	freopen("dijkstra.out", "w",stdout);
	scanf("%d", &n);
	int x, y, z;
	scanf("%d", &m);
	for(int i=1;i<=m;++i)  
    {
        scanf("%d %d %d", &x, &y, &z);
        add(x, y, z);
		//add(y, x, z);
	}
}

void swap(int x, int y)
{
    int t = h[x];
    h[x] = h[y];
    h[y] = t;
}

void upheap(int what)
{
    int tata;
    while ( what > 1 )
    {
        tata = what >> 1;

        if ( d[ h[tata] ] > d[ h[what] ] )
        {
            poz[ h[what] ] = tata;
            poz[ h[tata] ] = what;
            swap(tata, what);
            what = tata;
        }
        else
            what = 1;
    }
}

void downheap(int what)
{
    int f;
    while ( what <= k )
    {
        f = what;
        if ( (what<<1) <= k )
        {
            f = what << 1;
            if ( f + 1 <= k )
                if ( d[ h[f + 1] ] < d[ h[f] ] )
                    ++f;
        }
        else
            return;

        if ( d[ h[what] ] > d[ h[f] ] )
        {
            poz[ h[what] ] = f;
            poz[ h[f] ] = what;

            swap(what, f);

            what = f;
        }
        else
            return;
    }
}

void dijkstra_heap(int x)
{
    k=0;
	for ( int i = 1; i <= n; ++i )
		if(i!=x)
		{
			d[i] = inf;
			poz[i] = -1;
		}
	poz[x] = x;
    h[++k] = x;
    while ( k )
    {
        int min = h[1];
        swap(1, k);
        poz[ h[1] ] = 1;
        --k;
        downheap(1);
        graf *q = a[min];
        while ( q )
        {
            if ( d[q->nod] > d[min] + q->cost )
            {
                d[q->nod] = d[min] + q->cost;
                if ( poz[q->nod] != -1)
                    upheap( poz[q->nod] );
                else
                {
                    h[++k] = q->nod;
                    poz[ h[k] ] = k;
                    upheap( k );
                }
            }
            q=q->next;
        }
    }
}

int main()
{
    read();
	for(int x=1;x<=1;++x)
	{
		//for(int i=1;i<=n;++i)
			//d[i]=0;
		dijkstra_heap(x);
		for ( int i = 2; i <= n; ++i )
		{
			printf("%d ", d[i]);
			//if(d[i]>max && d[i]!=inf)
				//max=d[i];
		}	
		printf("\n");	
	}
	//printf("%d\n",max);
    return 0;
}