#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;


long fiuS(long parinte)
{
	return parinte*2;
}

long fiuD(long parinte)
{
	return parinte*2+1;
}

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 moveDown(long vf)
{
	long fius=fiuS(vf),fiud=fiuD(vf);
	long pozmin,ok=0;

	while(fius<=lg && ok==0)
	{
		pozmin=vf;

		if(dist[fius]<dist[vf])
			pozmin=fius;
		
		if(fiud<=lg && dist[fiud]<dist[pozmin])
			pozmin=fius;

		if(pozmin==vf)
			ok=1;
		else
		{
			swap(pozmin,vf);
			fiud=fiuD(pozmin);
			fius=fiuS(pozmin);
			vf=pozmin/2;
		}

	}

}

void moveUp(long vf)
{
	long parinte = vf/2;

	while(parinte>=1)
	{
		if(dist[parinte]>dist[vf])
			swap(parinte,vf);
		else
			parinte=-1;
		parinte/=2;
	}
}

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];
				heap.push_back(varf);
				pozInHeap[varf]=lg;
				moveUp(pozInHeap[varf]);
				//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;
}