#include<stdio.h>
#include<algorithm>

using namespace std;

const int maxn=50005;
const int inf=1<<30;

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

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


inline int left_son(int i)
{
	return 2*i;
}

inline int right_son(int i)
{
	return 2*i+1;
}
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()
{
	int x,y,z;
	freopen("dijkstra.in","r",stdin);
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d %d",&x,&y,&z);
		add(x,y,z);
	}
}

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(h[tata],h[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(h[what], h[f]);

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

int main()
{
	freopen("dijkstra.out","w",stdout);
	read();
	dijkstra_heap();
	for(int i=2;i<=n;i++)
		if(d[i]==inf) printf("0 ");
	else printf("%d ",d[i]);
}