#include<fstream>
#include<limits>
using namespace std;
#define inf 1000000
int n;
int C[20000][20000],d[50001];
void dijkstra(int x0) {
	int i,min,k,ok=1,viz[50001],tata[50001];
	for(i=1;i<=n;i++) {
		d[i]=C[x0][i];
		tata[i]=x0;
		viz[i]=0;
	}
	tata[x0]=0;
	viz[x0]=1;
	while(ok) {
		min=inf;
		for(i=1;i<=n;i++) 
			if(!viz[i] && min>d[i]) {
				min=d[i];
				k=i;
			}
		if(min!=inf) {
			viz[k]=i;
			for(i=1;i<=n;i++) {
				if(!viz[i] && d[i]>d[k]+C[k][i]) {
					d[i]=d[k]+C[k][i];
					tata[i]=k;
				}
			}
		}
		else ok=0;
	}
}
int main() {
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	int i,j,m,x,y,z,x0;
	f>>n>>m;
	x0=1;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++) {
			if(i!=j) C[i][j]=inf;
			else C[i][j]=0;
		}
	for(i=1;i<=m;i++) {
		f>>x>>y>>z;
		C[x][y]=z;
	}
	dijkstra(x0);
	for(i=2;i<=n;i++) 
		if(d[i]!=inf) g<<d[i]<<" ";
		else g<<0<<" ";
	return 0;
}