#include<fstream>
#define MAX 50001
#define inf 2000000
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct graf {
int node,cost;
graf *next;
}*a[MAX];
int n,m;
int h[MAX],poz[MAX],d[MAX] ,num;
void add(int origin,int destination, int cost)
{
	graf *c=new graf;
	c->node=destination;
	c->cost=cost;
	c->next=a[origin];
	a[origin]=c;
}
void read() {
int w,b,c;
f>>n>>m;
 for (int i=1; i<=m; i++)
 {	f>>w>>b>>c; add(w,b,c);}
 
}
void swap(int a, int b){ int t=h[a]; h[a]=h[b]; h[b]=t;}
void upheap(int k){
int father;
while (k>1 )
{
	father=k>>1;
	if (h[k]<h[father])
	{
		poz[h[k]]=father;
		poz[h[father]]=k;
		swap (k,father);
		k=father;
	}
	else k=1;
 }
}
void downheap(int k){
int mini,left,right;
while (k<=num){
	mini=k; left=k<<1; right=left+1;
	 if (left<num && h[left]<h[mini]) mini=left;
	 if (right<num && h[right]<h[mini]) mini=right;
	if (mini!=k)
		{
			poz[h[mini]]=k;
			poz[h[k]]=mini;
			swap(mini,k);
			k=mini;
		}
	else return;
}
}
void djikstraHeap(){
for (int i=2; i<=n; i++) {d[i]=inf; poz[i]=-1;}
d[1]=0; poz[1]=1;
h[++num]=1;
	while (num){
		int min=h[1];
		h[1]=h[num];
		--num;
		downheap(1);
		graf *q=a[min];
		while (q){
			if (d[q->node]>d[min]+q->cost){
				d[q->node]=d[min]+q->cost;
				if (poz[q->node]!=-1)
					upheap(poz[q->node]);
				else
				{ h[++num]=q->node;
				  poz[q->node]=num;
				  upheap(num);
				}	
			}
		q=q->next;
		}
	}
}
int main()
{
	read();
	djikstraHeap();
	for (int i=2; i<=n; i++)
		g<<d[i]<<" ";
	f.close();
	g.close();
	return 0;	
}