#include<cstdio>
#include<vector>
using namespace std;
int n,n1,m,d[50010],H[50010],poz[50010];
struct Muchie{int nod,cost;};
vector <Muchie> G[50010];

inline void Citire()
{
	int i,x,y,c;
	Muchie aux;
	freopen("dijkstra.in","r",stdin);
	scanf("%d %d",&n,&m);
	n1=n;
	for(i=1;i<=m;i++)
	{
		scanf("%d %d %d",&x,&y,&c);
		aux.nod=y; aux.cost=c;
		G[x].push_back(aux);
	}
}

inline void CombHeap(int i,int n)
{
	int x,tata,fiu;
	tata=i;
	fiu=2*i;
	x=H[tata];
	while(fiu<=n)
	{
		if(fiu<n)
			if(d[H[fiu]]>d[H[fiu+1]])
				fiu++;
		if(d[x]>d[H[fiu]])
		{
			H[tata]=H[fiu];
			poz[H[fiu]]=tata;
			tata=fiu;
			fiu=(fiu<<1);
		}
		else
			fiu=n+1;
	}
	H[tata]=x;
	poz[x]=tata;
}

inline int ExtractMin()
{
	int sol=H[1];
	H[1]=H[n--];
	CombHeap(1,n);
	return sol;
}

inline void Urca(int fiu,int x)
{
	int tata=(fiu>>1);
	while(tata && d[H[tata]]>d[x])
	{
		H[fiu]=H[tata];
		poz[H[tata]]=fiu;
		fiu=tata;
		tata=(fiu>>1);
	}
	H[fiu]=x;
	poz[x]=fiu;
}

inline void Creare_Heap()
{
	int i;
	for(i=1;i<=n;i++)
		H[i]=poz[i]=i;
	for(i=n/2;i>0;i--)
		CombHeap(i,n);
}

inline void Dijkstra()
{
	int i,j,vfmin,dmin;
	Muchie aux;
	for(i=2;i<=n;i++)
		d[i]=2000000000;
	d[1]=0;
	Creare_Heap();
	for(i=1;i<=n1;i++)
	{
		vfmin=ExtractMin();
		dmin=d[vfmin];
		for(j=0;j<G[vfmin].size();j++)
		{
			aux=G[vfmin][j];
			if(d[aux.nod]>dmin+aux.cost)
			{
				d[aux.nod]=dmin+aux.cost;
				Urca(poz[aux.nod],aux.nod);
			}				
		}
	}
}

inline void Afisare()
{
	int i;
	freopen("dijkstra.out","w",stdout);
	for(i=2;i<=n1;i++)
	{
		if(d[i]==2000000000)
			printf("0 ");
		else
			printf("%d ",d[i]);
	}
	printf("\n");
}

int main()
{
	Citire();
	Dijkstra();
	Afisare();
	return 0;
}