#include <stdio.h>
#include <vector>
using namespace std;

int n,m,i,a,b,c,vv[50010],z[50010],ii;
vector <int> g[50010];
vector <int> v[50010];
vector <int> q;
int in,sf;

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++){
		scanf("%d%d%d",&a,&b,&c);
		g[a].push_back(b);
		v[a].push_back(c);
	}
	in=sf=0;
	q.push_back(1);
	//printf("%d ",q[in]);
	for(i=2;i<=n;i++){
		vv[i]=250000;
	}
	while(in<=sf){
		z[q[in]]=0;
		//printf("%d ",q[in]);
		for(i=0;i<g[q[in]].size();i++){
			if(vv[g[q[in]][i]]>vv[q[in]]+v[q[in]][i]){
				vv[g[q[in]][i]]=vv[q[in]]+v[q[in]][i];
				if(z[g[q[in]][i]]==0){
					sf++;
					q.push_back(g[q[in]][i]);
					z[g[q[in]][i]]=1;
				}
			}
		}
		in++;
	}
	for(i=2;i<=n;i++){
		if(vv[i]!=250000){
			printf("%d ",vv[i]);
		}else{
			printf("0 ");
		}
	}
	return 0;
}