#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];

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[k].i]=pos[H[father(k)].i];
	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]=pos[H[s].i];
				H[k]=H[s];
				k=s;			
				}
			else  {
				pos[H[k].i]=pos[H[d].i];
				H[k]=H[d];
				k=d;
				} 
			}
		else {
			pos[H[k].i]=pos[H[s].i];
			H[k]=H[s];
			k=s;		
			}
		}
	else {
		if (d<=nn && H[k].val>H[d].val) {
			pos[H[k].i]=pos[H[d].i];
			H[k]=H[d];
			k=d;
			}
		else  break;
		}		
	
	}
H[k]=key;
pos[H[k].i]=k;
}



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;
H[1]=H[nn--];
down(1);
}

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 (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);
return 0;
}