#include <fstream>
#include <list>
#include <vector>

#define NMAX 50005

using namespace std;

long n,m,nev,vizitat[NMAX],varf;
long lung[NMAX];

struct Nod
{
	long vf;
	long lg;
	Nod(long nvf,long nlg)
	{
		vf=nvf;
		lg=nlg;
	}

};

vector<long> C[NMAX];
vector<long> V[NMAX];



long minim()
{
	long min=lung[1],i=2,svi=1;
	while(i<=n)
	{
		if(lung[i]<min && vizitat[i]==0)
		{
			min=lung[i];
			svi=i;
		}
		i++;
	}
	return svi;
}

int main()
{
	long i,x,y;
	long l;
	fstream fin,fout;
	fin.open("dijkstra.in",ios::in);
	fout.open("dijkstra.out",ios::out);


	fin>>n>>m;
	//for(i=0;i<n+1;i++)
	//{
	//	lst.push_back(new list<Nod*>);
	//	lung[i]=LONG_MAX;
	//}
	for(i=1;i<=n;i++)
	{
		lung[i]=LONG_MAX;
	}
	for(i=0;i<m;i++)
	{
		fin>>x>>y>>l;
	/*	lst[i]->push_back(new Nod(y,l));*/
		V[x].push_back(y);
		C[x].push_back(l);
		if(x==1)
			lung[y]=l;
	}
	vizitat[1]=1;
	while((varf=minim())!=1)
	{
		vizitat[varf]=1;
		//list<Nod*>::iterator itr;
		//for(itr=lst[varf]->begin(); itr!= lst[varf]->end(); itr++)
		//{
		//	if(lung[(*itr)->vf]>lung[varf]+lung[(*itr)->lg])
		//		lung[(*itr)->vf]=lung[varf]+lung[(*itr)->lg];
		//}
		vector<long>::iterator itr;
		long k=0;
		for(itr=V[varf].begin(); itr!=V[varf].end();itr++)
		{
			if(lung[(*itr)]>lung[varf]+C[varf][k])
				lung[(*itr)]=lung[varf]+C[varf][k];
			k++;
		}
	}

	for(i=2;i<=n;i++)
		fout<<lung[i]<<" ";
	fout<<'\n';

	fout.close();
	fin.close();
	return 0;
}