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

long n,m;
long d[NMAX],vizitat[NMAX];

struct nod
{
	long varf;
	long long cost;
	long iil; //al catelea nod este
	nod(){}
	nod(long nvarf,long long ncost,long niil)
	{
		varf=nvarf;
		cost=ncost;
		iil=niil;
	}
};

vector<list<nod> > G;
vector<nod> heap;
long pozitie[NMAX];

long pozD(long i)
{
	return i<<1+1;
}

long pozS(long i)
{
	return i<<1;
}

void swap(long poz1, long poz2)
{
	nod naux;
	long paux;

	naux=heap[poz1];
	heap[poz1]=heap[poz2];
	heap[poz2]=naux;

	paux=pozitie[heap[poz1].iil];
	pozitie[heap[poz1].iil]=pozitie[heap[poz2].iil];
	pozitie[heap[poz2].iil]=paux;
}

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

	while(parinte>=1 && d[heap[poz].varf] < d[heap[parinte].varf])
	{
		swap(poz,parinte);
		poz=parinte;
		parinte=poz/2;
	}
}

void moveDown(long poz)
{
	long r,l,pmin=-1;
	l=pozS(poz);
	r=pozD(poz);
//	while(l<=lg && (heap[poz].cost > heap[l].cost || heap[poz].cost > heap[r].cost))
	while(pmin!=poz && l<=lg)
	{
		pmin=poz;
		if(d[heap[pmin].varf] > d[heap[l].varf])
			pmin=l;

		if(r<=lg && d[heap[pmin].varf] > d[heap[r].varf])
			pmin=r;

		if(pmin!=poz)
		{
			swap(pmin,poz);
			poz=pmin;
			l=pozS(poz);
			r=pozD(poz);
		}
	}
}

//void updateHeap(nod tata, nod x)
//{
//	if(d[x.varf] > d[tata.varf]+tata.cost)
//	{
//		d[x.varf] = d[tata.varf]+x.cost;
//		moveUp(pozitie[x.iil]);
//	}
//}

void insereazaHeap(nod tata,nod x)
{
	if(d[x.varf] > d[tata.varf]+x.cost)
	{
		d[x.varf] = d[tata.varf]+x.cost;
		heap.push_back(x);
		pozitie[x.iil]=lg;
		moveUp(pozitie[x.iil]);
	}

}

void stergeHeap(long poz)
{
	heap[poz]=heap[lg];
	pozitie[heap[lg].iil]=0;
	pozitie[heap[poz].iil]=poz;
	heap.pop_back();
	moveUp(poz);
	moveDown(poz); //nu verifici daca e ultimul element
}

int main()
{
	fstream fin,fout;
	long i,x,y,c;
	nod nodul;
	fin.open("dijkstra.in",ios::in);
	fout.open("dijkstra.out",ios::out);
	list<nod> lista;
	heap.push_back(nod(0,0,0));
	fin>>n>>m;
	for(i=0;i<=n;i++)
	{
		G.push_back(lista);
		d[i]=LONG_MAX;
	}

	for(i=1;i<=m;i++)
	{
		fin>>x>>y>>c;
		G[x].push_back(nod(y,c,i));
	}

	d[1]=0;
	heap.push_back(nod(1,0,0));
	list<nod>::iterator itr;
	vizitat[1]=1;
	while(heap.size()!=1)
	{
		nodul=heap[1];
		stergeHeap(1);
		pozitie[nodul.iil]=0;
		for(itr=G[nodul.varf].begin(); itr!= G[nodul.varf].end(); itr++)
		{
			if(pozitie[nodul.iil]==0)
			{
				insereazaHeap(nodul,*itr);
				//vizitat[nodul.varf]=1;
			}
		/*	else
				updateHeap(nodul,*itr);*/
		}
	}

	for(i=2;i<=n;i++)
		if(d[i]==LONG_MAX)
			fout<<"0 ";
	else
		fout<<d[i]<<" ";
	fout<<'\n';
	fin.close();
	fout.close();
	return 0;
}