#include <cstdio>
#include <climits>
FILE *f=fopen("dijkstra.in","r");
FILE *g=fopen("dijkstra.out","w");
int i,j,L[250001],col[250001],C[250001],d[250001],s[250001],n,m,min,nod;

int main()
{
	fscanf(f,"%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		fscanf(f,"%d%d%d",&L[i],&col[i],&C[i]);
		if(L[i]==1)
			d[col[i]]=C[i];
		else
			if(col[i]==1)
				d[L[i]]=C[i];
	}
	for(i=2;i<=n;i++)
		if(d[i]==0)
			d[i]=INT_MAX;
	s[1]=0;
	
	for(i=1;i<n;i++)
	{
		min=INT_MAX;
		for(j=2;j<=n;j++)
			if(s[j]==0)
                if(d[j]<min)
                {
                    min=d[j];
                    nod=j;
                }
		s[nod]=1;
		for(j=1;j<=m;j++)
			if(L[j]==nod && !s[col[j]])
				if(min+C[j]<d[col[j]])
					d[col[j]]=min+C[j];
	}
	
	for(i=2;i<=n;i++)
		fprintf(g,"%d ",d[i]);
	return 0;
}