#include<iostream>
#include<fstream>
#include<vector>
using namespace std;

#define NMAX 50001
#define INF 1<<30

vector < pair < int , int > > v[NMAX];
int d[NMAX],p[NMAX],arb[4*NMAX+1],n,poz,ppoz;

void update(int nod, int st, int dr)
{
	int mij;
	if(st==dr) {
		arb[nod]=ppoz;
		return ;
	}
	mij=(st+dr)/2;
	if(poz<=mij)
		update(nod*2,st,mij);
	else update(nod*2+1,mij+1,dr);
	arb[nod]=arb[2*nod];
	if(d[arb[nod]]>d[arb[2*nod+1]])
		arb[nod]=arb[2*nod+1];
}

void dijkstra()
{
	int i,nod;
	for(i=2;i<=n;i++) {
		d[i]=INF;
		p[i]=INF;
	}
	d[0]=INF;
	for(i=1;i<=4*n;i++)
		arb[i]=0;
	d[1]=0;
	poz=1;
	ppoz=1;
	update(1,1,n);
	for(i=1;i<=n;i++) {
		nod=arb[1];
		poz=nod;
		ppoz=0;
		d[nod]=INF;
		update(1,1,n);
		for(vector < pair < int , int > > :: iterator it=v[nod].begin();it!=v[nod].end();it++) 
			if(p[it->first]>p[nod]+it->second) {
				p[it->first]=p[nod]+it->second;
				d[it->first]=p[nod]+it->second;
				ppoz=it->first;
				poz=it->first;
				update(1,1,n);
			}
	}
}
int main ()
{
	int i,m,x,y,cost;
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	f>>n>>m;
	for(i=1;i<=m;i++) {
		f>>x>>y>>cost;
		v[x].push_back(make_pair(y,cost));
	}
	f.close();
	dijkstra();
	for(i=2;i<=n;i++) {
		if(p[i]==INF)
			p[i]=0;
		g<<p[i]<<" ";
	}
	g.close();
	return 0;
}