#include<cstdio>
#include<vector>
using namespace std;
#define pp pair<int,int>
#define ff first
#define ss second
#define inf 100000000
#define nmax 50001
vector <pp> v[nmax];
int n,hp,m;
int d[nmax],H[nmax],poz[nmax];
inline int left_son(int k){
	return k<<1;
}
inline int right_son(int k){
	return (k<<1)+1;
}
inline int father(int k){
	return k>>1;
}
void build_heap(){
	for(int i=1;i<=hp;i++)
		H[i]=poz[i]=i;
}
void sift(int k){
	int son;
	do{
		son=0;
		if(left_son(k)<=hp)
			son=left_son(k);
		if(right_son(k)<=hp && d[H[son]]>d[H[right_son(k)]])
			son=right_son(k);
		if(d[H[son]]>d[H[k]])
			son=0;
		if(son){
			swap(poz[H[k]],poz[H[son]]);
			swap(H[k],H[son]);
			k=son;
		}
	}while(son);
}
int Min(){
	int key;
	key=H[1];
	swap(poz[H[1]],poz[H[hp]]);
	H[1]=H[hp--];
	sift(1);
	return key;
}
void percolate(int k){
	while(k>1 && d[H[k]]<d[H[father(k)]]){
		swap(poz[H[k]],poz[H[father(k)]]);
		swap(H[k],H[father(k)]);
		k=father(k);
	}
}
void Dijkstra(){
    int i,vfmin,dmin;
    for(i=2;i<=n;i++)
        d[i]=inf;
	d[1]=0;
	build_heap();
	for(i=1;i<=n;i++){
		vfmin=Min();
		dmin=d[vfmin];
		for(unsigned j=0;j<v[vfmin].size();j++){
			if(dmin+v[vfmin][j].ss<d[v[vfmin][j].ff]){
				d[v[vfmin][j].ff]=dmin+v[vfmin][j].ss;
				percolate(poz[v[vfmin][j].ff]);
			}
		}
	}
}
int main(){
    int i,a,b,c;
    freopen("dijkstra.in","r",stdin);
    scanf("%d%d",&n,&m);
	hp=n;
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        v[a].push_back(make_pair(b,c));
    }
    fclose(stdin);
    Dijkstra();
	freopen("dijkstra.out","w",stdout);
	for(i=2;i<=n;i++)
		printf("%d ",d[i]==inf ? 0:d[i]);
	return 0;
}