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

void moveUp(long poz)
{
	long pozs=poz/2,aux;
	while(pozs>=1 && dist[heap[poz]]<dist[heap[pozs]])
	{
		aux=heap[pozs];
		heap[pozs]=heap[poz];
		heap[poz]=aux;

		aux=pozInHeap[heap[pozs]];
		pozInHeap[heap[pozs]]=pozInHeap[heap[poz]];
		pozInHeap[heap[poz]]=aux;

		poz=pozs;
		pozs/=2;
	}
}

long fiuS(long parinte)
{
	return parinte<<1;
}

long fiuD(long parinte)
{
	return parinte<<1+1;
}

void moveDown(long poz)
{
	long poz_min,aux;
	if(dist[fiuS(poz)]>dist[fiuD(poz)])
		poz_min=fiuD(poz);
	else
		poz_min=fiuS(poz);

	while(poz_min<=lg && dist[heap[poz_min]]<dist[heap[poz]])
	{
		if(dist[fiuS(poz)]>dist[fiuD(poz)])
			poz_min=fiuD(poz);
		else
			poz_min=fiuS(poz);

		aux=heap[poz_min];
		heap[poz_min]=heap[poz];
		heap[poz]=aux;

		aux=pozInHeap[poz_min];
		pozInHeap[poz_min]=pozInHeap[poz];
		pozInHeap[poz]=aux;

		poz=poz_min;
	}
}

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

void stergeDinHeap(long x)
{

	pozInHeap[heap[1]]=-1;
	pozInHeap[heap[lg]]=0;
	
	heap[1]=heap[lg];
	heap.pop_back();
	if(!heap.empty())
		moveDown(1);
}

void dijkstra()
{
	while(heap.size()!=1)
	{
		long x=heap[1];
		stergeDinHeap(1);
		list<nod>::iterator i;

		for(i=G[x].begin(); i!=G[x].end(); i++)
		{
			if(dist[(*i).vf]>dist[x]+(*i).cost)
			{
				dist[(*i).vf]=dist[x]+(*i).cost;
				moveUp(pozInHeap[(*i).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;
}