#include<fstream>
#include<algorithm>
#include<vector>
#define Nmax 50001
#define inf 1<<30
#define val first
#define cost second
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
using namespace std;
int x,y,z,i,j,N,M,Nod,nr;
pair<int,int> Nod2;
vector <int> sol(Nmax),poz(Nmax),H(Nmax);
vector < pair<int,int> > a[Nmax];
vector < pair<int,int> >::iterator it;
void Swap(int a,int b)
{
	swap(H[a],H[b]);
	swap(poz[H[a]],poz[H[b]]);
}
void heap_up(int nod)
{
	while ( (nod>>1) && sol[H[nod>>1]]>sol[H[nod]] )
	{
		Swap(nod,nod>>1);
		nod>>=1;
	}
}
void heap_down(int nod)
{
	int Poz;
	while ((nod<<1)<=nr)
	{
		if ((nod<<1)+1<=nr && sol[H[(nod<<1)+1]]<sol[H[nod<<1]] ) Poz=(nod<<1)+1;
			else Poz=(nod<<1);
		if (sol[H[nod]]<=sol[H[Poz]]) return;			
		Swap(nod,Poz);
		nod=Poz;
	}
}
int main()
{
	in>>N>>M;
	for (i=1;i<=M;i++)
	{
		in>>x>>y>>z;
		a[x].push_back(make_pair(y,z));
	}
	for (i=1;i<=N;i++)
	{
		H[++nr]=i;
		poz[i]=i;
		sol[i]=inf;
	}
	sol[1]=0;
	while (nr)
	{
		Nod=H[1];
		Swap(1,nr--);
		heap_down(1);
		for (it=a[Nod].begin();it!=a[Nod].end();it++)
		{
			Nod2=*it;
			if (sol[Nod]+Nod2.cost<sol[Nod2.val])
			{
				sol[Nod2.val]=sol[Nod]+Nod2.cost;
				heap_up(poz[Nod2.val]);
			}
		}
	}		
	for (i=2;i<=N;i++)
		out<<((sol[i]!=inf) ? sol[i]:0)<<" ";
	return 0;
}