#include<fstream>
#include<algorithm>
#define M 2000000000
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct nod
{
	int inf,c;
	nod* leg;
};
typedef nod* PNod;
PNod L[50001];
int poz[50001],heap[50001],cost[50001],nodcur,n,m;
void interschimba(int x,int y)
{
	int aux;
	aux=heap[x];
	heap[x]=heap[y];
	heap[y]=aux;
	aux=poz[heap[x]];
	poz[heap[x]]=poz[heap[y]];
	poz[heap[y]]=aux;
	/*swap(heap[x],heap[y]);
	swap(poz[heap[x]],poz[heap[y]]);*/
}
void add(int x,int y,int z)
{
	PNod p=new nod;
	p->inf=y;
	p->c=z;
	p->leg=L[x];
	L[x]=p;
}
void heapup(int i)
{
	if(cost[heap[i/2]]<cost[heap[i]])return;
	interschimba(i,i/2);
	heapup(i/2);
}
void heapdown(int i)
{
	int st,dr;
        if(i*2>m) return;// daca am iesit din heap {1,2,...m}
        st=cost[heap[i*2]];//din arborele binar costul radacinei subarborelui stang
        if(i*2+1<=m)dr=cost[heap[i*2+1]];//din arborele binar costul radacinei subarborelui drept
			else dr=st+1;
        if(st<dr)
        {
                if(cost[heap[i]]<=st)return;//daca este bine ordonat renuntam la reordonare
                interschimba(i,2*i);// altfel ma duc pe subarborele stang
                heapdown(i*2);
        }
        else
        {
                if(cost[heap[i]]<=dr)return;
                interschimba(i,2*i+1);
                heapdown(2*i+1);
        }
	
}
int main()
{
	int i,a,b,costi;
	f>>n>>m;
	for(i=1;i<=m;i++)
	{	f>>a>>b>>costi;
		add(a,b,costi);
	}
	for(i=1;i<=n;i++)
	{
		cost[i]=M;// costul de la nodul 1, in cazul nostru, initial, este infinit spre toate
		heap[i]=i;//formam heap-ul
		poz[i]=i;//pozitiile nodului din heap
	}
	m=n;
	cost[1]=0;
	for(i=1;i<=n-1;i++)
	{
		nodcur=heap[1];// nodul curent este radacina arborelui(avem minheap)
		interschimba(1,m);// reducem heap-ul dupa ce folosim nodul curent
		m--;
		heapdown(1);// rearanjam heap-ul 
		for(PNod p=L[nodcur];p;p=p->leg)//parcurgem vecinii nodului curent (fosta radacina a arborelui)
		{
			if(cost[p->inf]>cost[nodcur]+p->c)// daca putem ajunge la un vecin de a  nodului curent prin nod cur cu un drum mai mic atunci reinitializam si rearanjam arborele
			{
				cost[p->inf]=cost[nodcur]+p->c;
				heapup(poz[p->inf]);// rearanjam arborele de pe pozitia vecinului nodului curent
			}
		}
	}
	for(i=2;i<=n;i++)
		if(cost[i]==M)
			g<<"0 ";
		else g<<cost[i]<<" ";
}