#include<fstream>
#include<list>
#include<vector>
#define NMAX 50005
#define lg (heap.size()-1)
using namespace std;

long n,m;
//
//struct nod
//{
//	long vf,cost;
//	nod(){}
//	nod(long nvf,long ncost)
//	{
//		vf=nvf; cost=ncost;
//	}
//};

vector<list<pair<long,long> > > G;

long long dist[NMAX]; 
vector<long> heap;
long pozInHeap[NMAX],vizitat[NMAX];
vector<long> C;


void swap(long poz1,long poz2)
{
	long aux;
	aux=pozInHeap[heap[poz1]];
	pozInHeap[heap[poz1]]=pozInHeap[heap[poz2]];
	pozInHeap[heap[poz2]]=aux;

	aux=heap[poz1];
	heap[poz1]=heap[poz2];
	heap[poz2]=aux;
}

void moveUp(long poz)
{
	long parinte=poz/2;
	
	while(parinte>=1)
	{
		if(dist[heap[parinte]]>dist[heap[poz]])
			swap(parinte,poz);
		else
			break;
		poz=parinte;
		parinte=parinte/2;
	}
}

void moveDown(long poz)
{
	long fius,fiud;
	long pozMin;
	
	do
	{

		fius=poz*2;
		fiud=poz*2+1;
		if(fius>lg)
			break;
		if(fiud>lg || dist[heap[fius]]<dist[heap[fiud]])
			pozMin=fius;
		else
			pozMin=fiud;

		if(dist[heap[poz]]>dist[heap[pozMin]])
			swap(poz,pozMin);
		else 
			break;
		poz=pozMin;

	}while(1);
}

void adaugaInHeap(long i)
{
	heap.push_back(i);
	pozInHeap[i]=lg;
	moveUp(lg);
}

void dijkstra()
{
	long el,varf;
	list<pair<long,long> >::iterator itr;
	pair<long,long> que;

	while(heap.size()!=1)
	{
		el=heap[1];
		pozInHeap[heap[1]]=-1;
		pozInHeap[heap[lg]]=1;

		heap[1]=heap[lg];
		heap.pop_back();
		moveDown(1);

		for(itr=G[el].begin(); itr!= G[el].end(); itr++)
		{
			que=*itr;
			varf=que.first;
			if( dist[varf]>que.second+dist[el])
			{
				dist[varf]=que.second+dist[el];
				moveUp(pozInHeap[varf]);
				if(vizitat[que.first]==0)
				{
					heap.push_back(varf);
					pozInHeap[varf]=lg;
					vizitat[que.first]=1;
				}
				//moveDown(pozInHeap[(*itr).vf]);
			}
		}
	}
}

int main()
{
	list<pair<long,long> > lista;
	long x,y,cost,i;

	fstream fin,fout;
	fin.open("dijkstra.in",ios::in);
	fout.open("dijkstra.out",ios::out);

	fin>>n>>m;

	heap.push_back(0);
	for(i=0;i<=n;i++)
	{
		G.push_back(lista);
		dist[i]=LONG_MAX;
		//if(i!=0)
		//{
		////	adaugaInHeap(i);
		//	//pozInHeap[i]=i;
		//}
	}
	adaugaInHeap(1);

	for(i=0;i<m;i++)
	{
		fin>>x>>y>>cost;
		G[x].push_back(make_pair(y,cost));
	}
	dist[1]=0;
	dijkstra();

	for(i=2;i<=n;i++)
		if(dist[i]==LONG_MAX)
			fout<<"0 ";
		else
			fout<<dist[i]<<" ";

	fout<<'\n';
	fin.close();
	fout.close();
	
	return 0;
}