#include<fstream>
#include<vector>
#define infin 2000
using namespace std;



ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int v[50002];
struct muchie
{
	int inf;
	int cost;
};
	
vector <muchie> lv[50002];
int pret[50002],aux;
int n,mm;


int poz[200000],heap[200000],ordin[200000],k=0,j=0;
void add(int cost,int nod)
{	
	poz[nod]=++j;
	ordin[j]=nod;
	heap[j]=cost;
	int j2;
	j2=j;
	while(j>1&&heap[j/2]>heap[j])
		{
			int aux;
			aux=heap[j/2];
			heap[j/2]=heap[j];
			heap[j]=aux;
			poz[ordin[j/2]]=j;
			poz[ordin[j]]=j/2;
			aux=ordin[j/2];
			ordin[j/2]=ordin[j];
			ordin[j]=aux;
			j=j/2;
		}
	j=j2;
}

void remove(int x)
{ 
	int u,p,aux;
	u=poz[x];
	heap[u]=heap[j];
	heap[j]=0;
	ordin[u]=ordin[j];
	poz[ordin[j]]=u;
	j--;
	while(heap[2*u]&&(heap[2*u]<heap[u]||(heap[2*u+1]&&heap[2*u+1]<heap[u])))
		{
			if(heap[2*u+1]&&heap[2*u+1]<heap[2*u])p=2*u+1;
				else p=2*u;
			aux=heap[p];
			heap[p]=heap[u];
			heap[u]=aux;
			poz[ordin[p]]=u;
			poz[ordin[u]]=p;
			aux=ordin[p];
			ordin[p]=ordin[u];
			ordin[u]=aux;
			u=p;
		}
}


int main()
{
	int i;
	
	fin>>n;
	fin>>mm;
	for(i=1;i<=mm;i++)
	{	
		int x;
		muchie y;
		fin>>x>>y.inf>>y.cost;
		lv[x].push_back(y);
	}
	add(0,1);
	pret[1]=0;
	for(i=2;i<=n;i++)
		{add(infin,i);
	     pret[i]=infin;
		}
	
	int j;
	
	while(heap[1]!=infin)
	{
		 int cine,cat;
		 cine=ordin[1];
		 
		 v[cine]=1;
		 cat=lv[cine].size();
		 for(i=0;i<cat;i++)
		 {
		 
			 if(!v[lv[cine][i].inf]&&pret[cine]+lv[cine][i].cost<pret[lv[cine][i].inf])
 			 {
				 pret[lv[cine][i].inf]=pret[cine]+lv[cine][i].cost;
				 remove(lv[cine][i].inf);
				 add(pret[lv[cine][i].inf],lv[cine][i].inf);
			 }
		 }
		 remove(cine);
		 add(infin,cine);
		
	 }
	 
	 for(i=2;i<=n;i++)
		{if(pret[i]!=infin)fout<<pret[i]<<" ";
	       else fout<<"0 ";
		}
		
		 
	
	return 0;
}