#include <cstdio>
#include <vector>
#include <utility>
#include <queue>
#define INF 100000000
using namespace std;
FILE *f,*g;
int n,m,nn;
typedef struct cp{int y,c;};
typedef struct cp2{int i,val;} ;
vector <cp> a[50010];
int V[50010];
cp2 H[50010];
int pos[50010];
int bf[50010];

inline int father(int n) {return n/2; }
inline int st(int n) {return n*2;}
inline int dr(int n) {return n*2+1;}

void up(int k) {
cp2 key=H[k];


while (k>1 && key.val<H[father(k)].val ) {
	pos[H[father(k)].i]=k;
	H[k]=H[father(k)];
	k=father(k);
	}
H[k]=key;
pos[H[k].i]=k;
}


void down(int k) {
int s,d;
cp2 key=H[k];

while (k<=nn) {
	s=st(k);
	d=s+1;

	if (s>nn) break;

	if (H[k].val>H[s].val) {
		if (d<=nn) {
			if (H[d].val>H[s].val) {
				pos[H[k].i]=s;
				pos[H[s].i]=k;
				swap(H[k],H[s]);
				k=s;
				}
			else  {
				pos[H[k].i]=d;
				pos[H[d].i]=k;
				swap(H[k],H[d]);
				k=d;
				}
			}
		else {
			pos[H[k].i]=s;
			pos[H[s].i]=k;
			swap(H[k],H[s]);
			k=s;
			}
		}
	else {
		if (d<=nn && H[k].val>H[d].val) {
			pos[H[k].i]=d;
			pos[H[d].i]=k;
			swap(H[k],H[d]);
			k=d;
			}
		else  break;
		}

	}
}



void read() {
int i,x;
cp ax;
fscanf(f,"%d%d",&n,&m);
for (i=1;i<=m;i++) {
	fscanf(f,"%d%d%d",&x,&ax.y,&ax.c);
	a[x].push_back(ax);
	}

}

void add(cp2 x) {

H[++nn]=x;
pos[x.i]=nn;
up(nn);
}


void cut() {
pos[H[1].i]=-1;
if (nn>1) {
    H[1]=H[nn--];
    pos[H[1].i]=1;
    down(1);
    }
else
    nn--;
}

void solve() {
int i,q;
cp2 ax,ax2;

for (V[1]=0,pos[1]=1,i=2;i<=n;i++) { V[i]=INF; pos[i]=-1; }
nn=1;
ax.i=1; ax.val=0;
H[1]=ax;

for (q=1;q<=n;q++) {
	ax=H[1];
	if (nn==0) break;
	cut();

	for (i=0;i<a[ax.i].size();i++)
		if (a[ax.i][i].c+ax.val < V[a[ax.i][i].y]) {
			V[a[ax.i][i].y]=a[ax.i][i].c+ax.val;
            if (V[a[ax.i][i].y]==2674) {
                q++;
                q--;
                }
			if (pos[a[ax.i][i].y]==-1) {
				ax2.val=V[a[ax.i][i].y];
				ax2.i=a[ax.i][i].y;
				add(ax2);
				}
			else {
				H[pos[a[ax.i][i].y]].val=V[a[ax.i][i].y];
				up(pos[a[ax.i][i].y]);
				}
			}

	}



}

void write() {
	int i;
for (i=2;i<=n;i++)
	fprintf(g,"%d ",V[i]!=INF?V[i]:0);
}

int main()  {
f=fopen("dijkstra.in","r");
g=fopen("dijkstra.out","w");


read();
solve();
write();

fclose(g);


fclose(g);
return 0;
}