#include <iostream>
#include <vector>
#include <list>

#define NMAX 50005
#define DMAX 0xfffffff

using namespace std;
typedef pair<int,int> pereche;
typedef list<pereche> lista;

vector<int> heap(NMAX),pozitie(NMAX,-1),distanta(NMAX,DMAX);
lista G[NMAX];
int M,N,iHeap=1;

void citire(),rezolvare(),afisare();

int main()
{
	
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	
	citire();
	rezolvare();
	afisare();
	
	return 0;
}

void afisare()
{
	for(vector<int>::iterator it=distanta.begin()+2;it<=distanta.begin()+N;it++)
		if(DMAX==*it)
			cout<<"0 ";
		else
			cout<<*it<<" ";
}

void hDown(int poz)
{
	for(;;)
	{
		int s=poz<<1,d=s+1,aux=s;
		
		if(s>=iHeap)
			return;
		else if(d<iHeap&&distanta[heap[s]]>distanta[heap[d]])
			aux=d;
		
		if(distanta[heap[poz]]>distanta[heap[aux]])
		{
			swap(heap[poz],heap[aux]);
			pozitie[heap[poz]]=aux;
			pozitie[heap[aux]]=poz;
			poz=aux;			
		}
		else
			return;
	}
}

int hOut()
{
	int aux=heap[1];
	heap[1]=heap[--iHeap];
	hDown(1);
	return aux;
}

void hUp(int poz)
{
	for(int tata=poz>>1;tata&&distanta[heap[tata]]>distanta[heap[poz]];tata=poz>>1)
	{
		swap(heap[tata],heap[poz]);
		pozitie[heap[tata]]=poz;
		pozitie[heap[poz]]=tata;
		poz>>=1;
	}
}

void hIn(int nr)
{
	heap[iHeap]=nr;
	pozitie[nr]=iHeap;
	hUp(iHeap);
	iHeap++;
}

void rezolvare()
{
	heap.push_back(123);
	hIn(1);
	distanta[1]=0;
	
	while(iHeap!=1)
	{
		int poz=hOut();
		for(lista::iterator it=G[poz].begin();it!=G[poz].end();it++)
			if(distanta[(*it).first]>distanta[poz]+(*it).second)
			{
				distanta[(*it).first]=distanta[poz]+(*it).second;
				if(pozitie[(*it).first]==-1)
					hIn((*it).first);
				else
					hUp(pozitie[(*it).first]);
			}
	}
}

void citire()
{
	int s,d,c;
	scanf("%d %d",&N,&M);
	for(int i=0;i<M;i++)
	{
		scanf("%d %d %d",&s,&d,&c);
		G[s].push_back(pereche(d,c));
	}
}