#include <fstream>
#define N 50010
#define M 250010

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

int d[N],arcx[M],arcy[M],i,n,m;
short arcd[M],c;

int main () {
	in>>n>>m;
	for (i=0; i<m; i++) in>>arcx[i]>>arcy[i]>>arcd[i];
	for (i=0; i<=n; i++) d[i]=-1; d[1]=0;
	while (!c) {
		c=1;
		for (i=0; i<m; i++)
			if (d[arcx[i]]>-1&&(d[arcy[i]]==-1||d[arcy[i]]>d[arcx[i]]+arcd[i])) {
				d[arcy[i]]=d[arcx[i]]+arcd[i];
				c=0;
			}
	}
	for (i=2; i<=n; i++)
		if (d[i]==-1) out<<"0 ";
		else out<<d[i]<<" ";
	return 0;
}