#include <fstream>
using namespace std;

#define inf 0xfffff

ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");

struct cell{long a,b,c;}a[250001];
long n,m,i,d[50001];


int main(){
	
	fi >> n >> m;
	for (i=1; i<=m; i++) {
		fi >> a[i].a >> a[i].b >> a[i].c;
		if(a[i].a==1) d[a[i].b]=a[i].c;  
	}
	
	for (i=1; i<=n; i++) if (!d[i]) d[i]=inf;
	
	int ok=0;
	while (!ok){
		ok=1;
		for (i=1; i<=m; i++)
			if (d[a[i].b]>d[a[i].a]+a[i].c){
				ok=0;
				d[a[i].b]=d[a[i].a]+a[i].c;
			}
	}
	
	for (i=2; i<=n; i++) fo << (d[i]<inf ? d[i]:0) << " ";
	
	return 0;
}