#include <fstream>
#include <vector>
#define Inf 2000000000
#define N 50010

std::ifstream in ("dijkstra.in");
std::ofstream out ("dijkstra.out");

std::vector<int> a[N],b[N];
int h[N],p[N],d[N],n,m,i,j,k,t,nh,z;

void swap (int x,int y) {
	p[h[x]]=y; p[h[y]]=x;
	z=h[x]; h[x]=h[y]; h[y]=z;
}

void up (int x) {
	if (x>1&&d[h[x>>1]]>d[h[x]]) {
		swap (x,x>>1);
		up (x>>1);
	}
}

void down (int x) {
	if (x<<1>nh) return;
	int y=x;
	if (d[h[x]]>d[h[x<<1]]) y=x<<1;
	if ((x<<1)+1<=nh&&d[h[y]]>d[h[(x<<1)+1]]) y=(x<<1)+1;
	if (y!=x) {
		swap (x,y);
		down (y);
	}
}

int main () {
	in>>n>>m;
	nh=n;
	while (m--) {
		in>>i>>j>>k;
		a[i].push_back (j);
		b[i].push_back (k);
	}
	for (i=1; i<=n; i++) {
		d[i]=Inf;
		h[i]=p[i]=i;
	}
	d[1]=0;
	while (nh) {
		k=h[1];
		if (d[k]==Inf) break;
		for (t=0; t<a[k].size (); t++) {
			j=a[k][t];
			if (p[j]<=nh) {
				z=b[k][t];
				if (d[k]+z<d[j]) {
					d[j]=d[k]+z;
					up (p[j]);
				}
			}
		}
		swap (1,nh);
		nh--;
		down (1);
	}
	for (i=2; i<=n; i++) {
		if (d[i]==Inf) out<<"0 ";
		else out<<d[i]<<" ";
	}
	out<<"\n";
	return 0;
}