#include<algorithm>
using namespace std;

#define DIM 50001
#define INF 1000001

struct djk{
	int d,f,poz;};

struct graf{
	int nod,cost;
	graf *urm;};

int n,m,cnt,h[DIM];
djk a[DIM];
graf *lst[DIM];

inline int fath(int k){

	return k>>1;}

inline int lson(int k){

	return k<<1;}

inline int rson(int k){

	return k<<1+1;}

void add(int a,int b,int c){
    graf *p=new graf;

    p->nod=b;
    p->cost=c;
    p->urm=lst[a];
    lst[a]=p;}

void swap(int a,int b){
	int aux;

	aux=h[a];
	h[a]=h[b];
	h[b]=aux;}

int uph(int k){
	int poz;

	for(poz=h[k]; k>1&&a[h[k]].d<a[h[fath(k)]].d; k=fath(k))
		h[k]=h[fath(k)];
	h[k]=poz;
	return k;}

void downh(int k){
	int poz,son;

	poz=h[k];
	do{
		son=0;
		if(lson(k)<=cnt){
			son=lson(k);
			if(rson(k)<=cnt&&a[h[rson(k)]].d<a[h[lson(k)]].d)
				son=rson(k);
			if(a[h[son]].d>=a[h[k]].d)
				son=0;}
		if(son){
			h[k]=h[son];
			k=son;}}
	while(son);
	h[k]=poz;}

void upd(int k){

	if(k>1&&a[h[k]].d<a[h[fath(k)]].d)
		uph(k);
	else
		downh(k);}

int insert(int poz){

	h[++cnt]=poz;
	return uph(cnt);}

void cut(int k){

	h[k]=h[cnt--];
	upd(k);}

void init(){
	int i;

	for(i=2; i<=n; ++i)
		a[i].d=INF;}

void dijkstra(){
	int aux;
    graf *p;

	a[1].poz=1;
    for(h[++cnt]=1; cnt; ){
		aux=h[1];
		cut(1);
        a[aux].f=1;
		for(p=lst[aux]; p; p=p->urm)
			if(a[aux].d+p->cost<a[p->nod].d){
				a[p->nod].d=a[aux].d+p->cost;
				if(!a[p->nod].f)
                    if(!a[p->nod].poz)
					   a[p->nod].poz=insert(p->nod);
				    else
					   upd(a[p->nod].poz);}}}

void solve(){
	int i,x,y,z;

	scanf("%d%d",&n,&m);
	for(i=0; i<m; ++i){
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);}
	init();
	dijkstra();}

void print(){
	int i;

	for(i=2; i<=n; ++i){
		if(a[i].d==INF)
			a[i].d=0;
		printf("%d ",a[i].d);}}

int main(){

	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);

	solve();
	print();
	
	return 0;}