// Algoritmul lui Dijkstra.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include "stdio.h"

FILE *f=fopen("dijkstra.in", "r");
FILE *g=fopen("dijkstra.out", "w");


typedef struct nod
{
	int x;
	int d;
	struct nod *adr;
};

nod *l[50001];


int n, m;
int viz[50001], sol[50001], vpoz[50001], nr, poz[50001], r[50001];
int fin;


void add(int x, int y, int d)
{
	nod *p=new nod;
	p->x=y;
	p->d=d;
	p->adr=l[x];
	l[x]=p;
}


void read()
{
	fscanf(f, "%d%d", &n, &m);
	for (int i=1; i<=m; i++)
	{
		int x, y, d;
		fscanf(f, "%d%d%d", &x, &y, &d);
		add(x, y, d);
		add(y, x, d);
	}

	for (int j=1; j<=n; j++)
	{
		sol[j]=10000000;
		vpoz[j]=j;
		poz[j]=j;
	}
}



void dijkstra()
{
	sol[1]=0;
	int cr=1;
	int ok=1;
	while (ok)
	{
		viz[cr]=1;
		nr++;

		int csol=sol[1];
		r[poz[1]]=sol[1];

		sol[1]=sol[n-nr+1];
		sol[n-nr+1]=0;
		poz[1]=poz[n-nr+1];
		vpoz[poz[1]]=1;
		poz[n-nr+1]=0;		
		int tata=1;
		int fiu=2;
		if (fiu<=n-nr && sol[fiu]>sol[fiu+1])
			fiu++;
		while (sol[tata]>sol[fiu] && fiu<=n-nr)
		{
				int h=sol[tata]; sol[tata]=sol[fiu]; sol[fiu]=h;
				h=poz[tata]; poz[tata]=poz[fiu]; poz[fiu]=h;
				vpoz[poz[tata]]=tata;
				vpoz[poz[fiu]]=fiu;
				tata=fiu;
				fiu=tata*2;
				if (fiu<=n-nr && sol[fiu]>sol[fiu+1])
					fiu++;
		}



		nod *p=l[cr];
		while (p!=NULL)
		{
			if (csol+p->d<sol[vpoz[p->x]] && !viz[p->x])
			{
				sol[vpoz[p->x]]=csol+p->d;
				int fiu=vpoz[p->x];
				int tata=fiu/2;
				while (sol[tata]>sol[fiu] && tata>0)
				{
					int h=sol[tata]; sol[tata]=sol[fiu]; sol[fiu]=h;
					h=poz[tata]; poz[tata]=poz[fiu]; poz[fiu]=h;
					vpoz[poz[tata]]=tata;
					vpoz[poz[fiu]]=fiu;
					fiu=tata;
					tata=fiu/2;
				}
			}
			p=p->adr;
		}

		cr=poz[1];

		if (nr==n)
		{
			ok=0;
		}

	}

}




int main()
{
	read();
	fin=5;
	dijkstra();
	for (int i=2; i<=n; i++)
		fprintf(g, "%d ", r[i]);
	return 0;
}