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

long long dist[NMAX]; 
vector<long> heap;
long pozInHeap[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[poz1];
	pozInHeap[poz1]=pozInHeap[poz2];
	pozInHeap[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);
		poz=parinte;
		parinte=parinte/2;
	}
}

void moveDown(long poz)
{
	long fius=fiuS(poz),fiud=fiuD(poz),ok=0;
	long pozMin;
	
	do
	{
		fius=fiuS(poz);
		fiud=fiuD(poz);
		if(fiud>lg)
			break;
		if(dist[heap[fius]]<dist[heap[fiud]])
			pozMin=fius;
		else
			pozMin=fiud;

		if(dist[heap[poz]]>dist[heap[pozMin]])
		{
			swap(poz,pozMin);
			ok=1;
		}
		poz=pozMin;

	}while(ok==1);
}

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

void dijkstra()
{
	long el;
	list<nod>::iterator itr;

	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++)
		{
			if(dist[(*itr).vf]>(*itr).cost+dist[el])
			{
				dist[(*itr).vf]=(*itr).cost+dist[el];
				moveUp(pozInHeap[(*itr).vf]);
				moveDown(pozInHeap[(*itr).vf]);
			}
		}
	}
}

int main()
{
	list<nod> 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;
		}
	}

	for(i=0;i<m;i++)
	{
		fin>>x>>y>>cost;
		G[x].push_back(nod(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;
}