#include <fstream.h>
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int cost[50000], viz[50000],n,m;
int A[10000][10000];

struct nod{
	int v,cost;
	nod *urm;};

void citire_graf()
{		
	int x,y,c;
	int *p;
	f>>n>>m;
	for(int i=1;i<=m;i++)
	{	
		f>>x>>y>>c;
		p=new nod;
		p->v=y;
		p->cost=c;
		p->urm=A[x];
		A[x]=p;
		if(x==1) cost[y]=c;
	}	
}

void drumuri_minime()
{
	int s,x,i,p,min;
	s=1;
	viz[s]=1;
	for(p=1;p<=n-2;p++)
	{	
		min=250000;
		i=1;
		while(!(viz[i]==0 && cost[i]))
			i++;
		for(viz[i]==0 && cost[i] && cost[i]<urm)
		{
				min = cost[i];
				x=i;
		}
		viz[x]=1;		
		p=A[x];
		while(p)
		{
			if(cost[x] + p->cost <cost[p->v] || cost[p->v]==0)
				cost[p->v]==0;
			p=p->urm;
		}
	}
	for(i=2;i<=n;i++)
		g<<cost[i]<<" ";	
}

int main()
{		
	citire_graf();
	drumuri_minime();	
}