#include<fstream>
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct nod{int inf,c;nod *urm;};
nod *l[1000];

int n,m,r,nh;
int d[1000],t[1000],poz[1000],x[1000];

void add(int nod1,int nod2,int cost)
{
	nod *q;
	
	q=new nod;
	q->inf=nod2;
	q->c=cost;
	
	q->urm=l[nod1];
	l[nod1]=q;
}

void cit()
{
	int i;
	int nod1,nod2,cost;
	
	fin>>n>>m;
	r=1;
	
	for(i=1;i<=n;i++)
    {
	   d[i]=999999;
	   x[i]=i;
	   poz[i]=i;
    }
	
	for(i=1;i<=m;i++)
	{
		fin>>nod1>>nod2>>cost;
		add(nod1,nod2,cost);
		add(nod2,nod1,cost);
		
		if(nod1==r) d[nod2]=cost,t[nod2]=r;
		if(nod2==r) d[nod1]=cost,t[nod1]=r;
	}
}

void swap(int i,int j)
{
	int aux;
	
	aux=x[i];
	x[i]=x[j];
	x[j]=aux;
	
	poz[x[i]]=j;
	poz[x[j]]=i;
}

void HeapUp(int k)
{
	int i;
	
	if(k<=1) return;
	
	i=k/2;
	if(d[x[k]]<d[x[i]])
	{
		swap(k,i);
		HeapUp(i);
	}
}

void BuildH(int k)
{
	int i;
	
	for(i=1;i<=k;i++)
		HeapUp(i);
}

void HeapDw(int r,int k)
{
	int st,dr,i;
	int poz1=2*r,poz2=2*r+1;
	
	if(poz1<=k)
	{
		st=x[poz1];
		if(poz2<=k)
			dr=x[poz2];
		else
			dr=-1;
		
		if(d[st]<d[dr] || dr==-1) i=poz1;
		else
			i=poz2;
		
		if(d[x[r]]>d[x[i]])
		{
			swap(r,i);
			HeapDw(i,k);
		}
	}
	else
		return;
}
	
int scoate_heap()
{
	swap(1,nh);
	poz[x[nh]]=0;
	nh--;
	
	HeapDw(1,nh);
	return x[nh+1];
}

void dijkstra()
{
   int i,k;
   nod *p;
   

	
   d[r]=0; nh=n;
   BuildH(n);
   
   while(nh>0)
   {
	   k=scoate_heap();
	   p=l[k];
	   
	   while(p)
	   {
		   if(d[p->inf]>d[k]+p->c && poz[p->inf])
		   {
			   d[p->inf]=d[k]+p->c;
			   t[p->inf]=k;
			   HeapUp(poz[p->inf]);
		   }
		   
		   p=p->urm;
	   }
   }
}
   
void print(int k)
{
	if(k>0)
	{
		print(t[k]);
		fout<<k<<" ";
	}
}

void afis()
{
	int i;
	
	for(i=1;i<=n;i++)
		if(i!=r)
		{
			//print(i);
			//fout<<"cost="<<d[i];
			//fout<<'\n';
			fout<<d[i]<<" ";
		}
}	



int main()
{
	cit();
	dijkstra();
	afis();
	
	
	fin.close();
	fout.close();
	return 0;
}