#include <cstdio>
#include <vector>
#define INF "dijkstra.in"
#define OUF "dijkstra.out"
#define pb(arg) push_back(arg)
#define sz(arg) arg.size()
#define MIN(a,b) ((a<b)?(a):(b))
#define CMP(nx,ny) ((dr[nx]<dr[ny])?(1):(0))
#define ST(arg)  (arg<<1)
#define DR(arg)  (arg<<1|1)
#define DAD(arg) (arg>>1)
using namespace std;

const int NMAX=50002;
const int MMAX=250002;
struct arc
{
	int nb,cs;
};
vector<arc> a[NMAX];

int n,dim,h[NMAX],hp[NMAX],dr[NMAX];
char viz[NMAX]={0};

void lift(int poz)
{
	int i,p,vp;
	i=poz;p=h[i];;
	while(i>1&&CMP(p,h[DAD(i)]))
	{
		h[i]=h[DAD(i)];
		hp[h[i]]=i;
		i=DAD(i);
	}
	h[i]=p;hp[h[i]]=i;
}

void sink(int poz)
{
	int l,r,best,aux;
	best=poz;
	l=ST(poz);r=DR(poz);
	if(l<=dim&&CMP(h[best],h[l])) best=l;
	if(r<=dim&&CMP(h[best],h[r])) best=r;
	if(best!=poz)
	{
		hp[h[poz]]=best;hp[h[best]]=poz;
		aux=h[poz];h[poz]=h[best];h[best]=aux;
		sink(best);
	}
}

void insert(int nd)
{
	h[++dim]=nd;
	lift(dim);
}

int extract()
{
	int ret=-1;
	if(dim)
	{
		ret=h[1];
		h[1]=h[dim--];
		if(dim) sink(1);
	}
	return ret;
}

void dijkstra(int snd)
{
	int i,nd,nb,cs;
	dim=0;
	dr[snd]=0;insert(snd);viz[snd]=1;
	while(dim)
	{
		nd=extract();
		for(i=0;i<sz(a[nd]);++i)
		{
			nb=a[nd][i].nb;cs=a[nd][i].cs;
			if(!viz[nb])
			{
				viz[nb]=1;dr[nb]=dr[nd]+cs;
				insert(nb);
			}
			else if(dr[nd]+cs<dr[nb])
			{
				dr[nb]=dr[nd]+cs;
				lift(hp[nb]);
			}
		}
	}
}
				
int main()
{
	FILE *in,*out;
	in=fopen(INF,"r");
	out=fopen(OUF,"w");
	int i,m,x,y,z;
	arc aux;
	
	fscanf(in,"%d%d",&n,&m);
	for(i=1;i<=m;++i)
	{
		fscanf(in,"%d%d%d",&x,&y,&z);
		aux.nb=y;aux.cs=z;
		a[x].pb(aux);
	}
	
	for(i=1;i<=n;++i) dr[i]=0;
	dijkstra(1);
	
	for(i=2;i<=n;++i) fprintf(out,"%d ",dr[i]);
	fclose(in);fclose(out);
	return 0;
}