#include<fstream>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
struct nod
{int info,cost; nod *urm;};
nod *a[50001];
int n,m,k,h[50001],d[50001],poz[50001],inf=1<<30;

void init()
{
for(int i=1;i<=n;i++)
	a[i]=NULL; 
}
void adauga_nod(int x,int y,int c)
{nod *p=new nod;
p->info=y;
p->cost=c;
p->urm=a[x];
a[x]=p;
}


void schimba(int x,int y)
{int aux=h[x];
h[x]=h[y];
h[y]=aux;
}

void upheap(int x)
{int tata;
while(x>1)
	{tata=x>>1;
	if(d[h[tata]]>d[h[x]])
		{poz[h[x]]=tata;
		poz[h[tata]]=x;
		schimba(tata,x);
		x=tata;
		}
	else x=1;
	}
}
	
	
void downheap(int x)
{int f;
while(x<=k)
	{f=x;
	if(x<<1<=k)
		{f=x<<1;
		if(f+1<=k)
			if(d[h[f+1]]<d[h[f]])
				++f;
		}
	else return;
	if(d[h[x]]>d[h[f]])
		{poz[h[x]]=f;
		poz[h[f]]=x;
		schimba(x,f);
		x=f;
		}
	else return;
	}
}

void dijkstra_heap()
{for(int i=2;i<=n;i++)
	{d[i]=inf;
	poz[i]=-1;
	}
poz[1]=1;
h[++k]=1;
while(k)
	{int min=h[1];
	schimba(1,k);
	poz[h[1]]=1;
	--k;
	downheap(1);
	nod *p=a[min];
	while(p)
		{if(d[p->info]>d[min]+p->cost)
			{d[p->info]=d[min]+p->cost;
			if(poz[p->info]!=-1)
				upheap(poz[p->info]);
			else
				{h[++k]=p->info;
				poz[h[k]]=k;
				upheap(k);
				}
			}
		p=p->urm;
		}
	}
}

	

int main()
{int i,j,c;
fin>>n>>m;
init();
for(int l=1;l<=m;l++)
	{fin>>i>>j>>c;
	adauga_nod(i,j,c);
	}
	
dijkstra_heap();
for(i=2;i<=n;i++)
	fout<<d[i]<<" ";
fout<<endl;

fin.close();
fout.close();
return 0;
}