#include<fstream.h>
#define nmax 5002
#define mmax 250002
#define inf 200000000
long long n,m,a[nmax][nmax],dn,di[nmax];
struct dist
{long long d;
int nod;} d[nmax];
void cit()
{
	long long k,i,j;
	ifstream fin("dijkstra.in");
	fin>>n>>m;
	for(k=1;k<=m;k++)
	{
		fin>>i>>j>>a[i][j];
		a[j][i]=a[i][j];
	}
	fin.close();
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(a[i][j]==0&&i!=j)
				a[i][j]=inf;
	for(i=2;i<=n;i++)
		{d[i-1].nod=i;d[i-1].d=a[1][i];}
}
void CombHeap(int i,int n)
{
	long long tata=i,fiu=2*i;
	dist v=d[i];
	while(fiu<=n)
	{
		if(fiu<n)
			if(d[fiu].d>d[fiu+1].d)
				fiu++;
		if(v.d>d[fiu].d)
		{
			d[tata]=d[fiu];
			tata=fiu;
			fiu=2*fiu;
		}
		else
			fiu=n+1;
	}
	d[tata]=v;
}
void CreareHeap()
{
	long long i;
	for(i=dn/2;i>=1;i--)
		CombHeap(i,dn);
}
dist extract_max()
{
	dist v=d[1];
	d[1]=d[dn--];
	CombHeap(1,dn);
	return v;
}
void dijkstra_heap()
{
	long long i,k;
	dist j;
	for(k=1;k<=n-1;k++)
	{
		j=extract_max();
		if(j.d!=inf)
		{di[j.nod]=j.d;
		for(i=1;i<=dn;i++)
			if(j.d+a[d[i].nod][j.nod]<d[i].d)
				d[i].d=j.d+a[d[i].nod][j.nod];
		}
		else
			di[j.nod]=0;
	}
}
void afis()
{
	int i;
	ofstream fout("dijkstra.out");
	for(i=2;i<=n;i++)
		fout<<di[i]<<" ";
	fout<<'\n';
	fout.close();
}
int main()
{
	cit();
	dn=n-1;
	CreareHeap();
	dijkstra_heap();
	afis();
	return 0;
}