#include<cstdio>
#include<vector>

using namespace std;

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

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

int 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 citire()
{
	scanf("%d%d",&n,&m);
	int x,y,z;
	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;
	while(k)
	{
		int minim=h[1];
		swap(h[1],h[k]);
		poz[h[1]]=1;
		--k;
		downheap(1);
		
		graf *q=a[minim];
		
		while(q)
		{
			if(d[q->nod]>d[minim]+q->cost)
			{
				d[q->nod]=d[minim]+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()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	citire();
	dijkstra_heap();
	
	for(int i=2;i<=n;i++)
		printf("%d ",d[i]);
	printf("\n");
}