#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,y,z;

void up (int x) {
	while (x>1&&d[h[y=(x>>1)]]>d[h[x]]) {
		p[h[x]]=y; p[h[y]]=x;
		z=h[x]; h[x]=h[y]; h[y]=z;
		x=y;
	}
}

void down (int x) {
	while (1) {
		z=x<<1;
		if ((z)<=nh&&d[h[x]]>d[h[z]]) y=z;
		if ((z)<nh&&d[h[y]]>d[h[z+1]]) y=z+1;
		if (x==y) break;
		p[h[x]]=y; p[h[y]]=x;
		z=h[x]; h[x]=h[y]; h[y]=z;
		x=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];
		p[h[1]]=nh; p[h[nh]]=1;
		z=h[1]; h[1]=h[nh]; h[nh]=1;
		nh--;
		down (1);
		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]);
				}
			}
		}
	}
	for (i=2; i<=n; i++) {
		if (d[i]==Inf) out<<"0 ";
		else out<<d[i]<<" ";
	}
	out<<"\n";
	return 0;
}