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

std::ifstream in ("grader_test10.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,nh;

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

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

void down (int x) {
	if (2*x>nh) return;
	int y=x;
	if (d[h[x]]>d[h[2*x]]) y=2*x;
	if (2*x+1<=nh&&d[h[y]]>d[h[2*x+1]]) y=2*x+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];
		for (j=0; j<a[k].size (); j++)
			if (p[a[k][j]]<=nh) {
				if (d[k]+b[k][j]<d[a[k][j]]) {
					d[a[k][j]]=d[k]+b[k][j];
					up (p[a[k][j]]); down (p[a[k][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;
}