#include<fstream>
#include<queue>
using namespace std;
#define NMAX 50002
#define MMAX 250 002

typedef struct{unsigned int nod,dist;} dij;
bool operator<(dij x, dij y){
	if(x.dist!=y.dist) return x.dist>y.dist;
	if(x.nod!=y.nod) return x.nod<y.nod;
	return false;
}

unsigned int c[NMAX],n;
bool s[NMAX];
priority_queue<dij> q;

vector<dij> a[50002];

void dijkstra(){
	dij x,y;
	unsigned int i;
	x.nod=1; x.dist=0;
	q.push(x);
	do{
		x=q.top();
		q.pop();
		if(!s[x.nod]){
			s[x.nod]=1; c[x.nod]=x.dist;
			for(i=0;i<a[x.nod].size();++i)
				if(!s[a[x.nod][i].nod]){
					y.nod=a[x.nod][i].nod; y.dist=x.dist+a[x.nod][i].dist;
					q.push(y);
				}
		}
	}while(!q.empty());
}



int main(){
	unsigned int  i,m;
	unsigned int x;
	dij p;
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	f>>n>>m;
	for(i=1;i<=m;++i){
		f>>x>>p.nod>>p.dist;
		a[x].push_back(p);
	}
	dijkstra();
	for(i=2;i<=n;++i)
		g<<c[i]<<' ';
}