#include <cstdio>
#define MaxN 50001
#define Inf 20000001

using namespace std;

int n,m,k,heap[MaxN],cost[MaxN],poz[MaxN];

struct nod
{
	int x,c;
	nod *urm;
};

nod *G[MaxN];

void add(int x,int y,int c)
{
	nod *aux=new nod;
	aux->x=y;
	aux->c=c;
	aux->urm=G[x];
	G[x]=aux;
}	

void cit()
{
	int x,y,c;
	freopen("dijkstra.in","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&c);
		add(x,y,c);
	}
}

void swap(int x,int y)
{
	int aux=heap[x];
	heap[x]=heap[y];
	heap[y]=aux;
}

void urca_heap(int nod)
{
	int t;
	while(nod>1)
	{
		t=nod/2;
		if(cost[heap[t]]>cost[heap[nod]])
		{
			poz[heap[nod]]=t;
			poz[heap[t]]=nod;
			swap(t,nod);
			nod=t;
		}
		else
			nod=1;
	}
}
	
void coboara_heap(int nod)
{
	int f;
	
	while(nod<=k)
	{
		f=nod;
		if(2*nod<=k)
		{
			f=2*nod;
			if(f+1<=k)
			{
				if(cost[heap[f]]>cost[heap[f+1]])
					f++;
			}
		}
		else
			return;
		if(cost[heap[nod]]>cost[heap[f]])
		{
			poz[heap[nod]]=f;
			poz[heap[f]]=nod;
			swap(nod,f);
			nod=f;
		}
		else
			return;
	}
}

void sol()
{
	int i,min;
	nod *aux;
	for(i=2;i<=n;i++)
	{
		cost[i]=Inf; poz[i]=-1;
	}
	poz[1]=1;
	heap[++k]=1;
	
	while(k)
	{
		min=heap[1];
		swap(1,k);
		poz[heap[1]]=1;
		k--;
		
		coboara_heap(1);
		aux=G[min];
		while(aux)
		{
			if(cost[aux->x]>cost[min]+aux->c)
			{
				cost[aux->x]=cost[min]+aux->c;
				if(poz[aux->x]!=-1)
					urca_heap(poz[aux->x]);
				else
				{
					heap[++k]=aux->x;
					poz[heap[k]]=k;
					urca_heap(k);
				}
			}
			aux=aux->urm;
		}
	}
}

void afis()
{
	freopen("dijkstra.out","w",stdout);
	for(int i=2;i<=n;i++)
		if(cost[i]==Inf)
			printf("%d ",0);
		else
			printf("%d ",cost[i]);
}

int main()
{
	cit();
	sol();
	afis();
	return 0;
}