#include<cstdio>
#include<vector>
#include<utility>
using namespace std;
#define nmax 50001
#define oo 1<<30
int n,m,d[nmax],h[nmax],H[nmax],nr;
vector<pair<int,int> > a[nmax];
void citire()
{
	int i,x,y,c;
	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", &x, &y, &c);
		a[x].push_back(make_pair(y,c));
	}
}
void insert(int);
void refresh(int);
int main()
{
	int i,nod;
	vector<pair<int,int> >::iterator it;
	citire();
	for(i=1;i<=n;i++)
	{
		d[i]=oo;
		h[i]=i;
		H[i]=i;
	}
	d[1]=0;
	nr=n;
	while(nr)
	{
		nod=h[1];
		for(it=a[nod].begin();it!=a[nod].end();it++)
			if(d[it->first]>d[nod]+it->second)
			{
				d[it->first]=d[nod]+it->second;
				insert(H[it->first]);
			}
		h[1]=h[nr];
		H[h[1]]=1;
		nr--;
		refresh(1);
	}
	for(i=2;i<=n;i++)
		if(d[i]==oo)
			printf("0 ");
		else
			printf("%d ", d[i]);
	return 0;
}	
void insert(int child)
{
	int dad,aux;
	for(;;)
	{
		dad=child/2;
		if(d[h[dad]]<=d[h[child]])
			return;
		aux=h[dad];
		h[dad]=h[child];
		h[child]=aux;
		H[h[dad]]=dad;
		H[h[child]]=child;
		child=dad;
	}
}
void refresh(int dad)
{
	int child,aux;
	for(;;)
	{
		child=dad*2;
		if(child>nr)
			return;
		if(child<nr)
			if(d[h[child+1]]<d[h[child]])
				child++;
		if(d[h[dad]]<=d[h[child]])
			return;
		aux=h[dad];
		h[dad]=h[child];
		h[child]=aux;
		H[h[dad]]=dad;
		H[h[child]]=child;
		dad=child;
	}
}