#include<stdio.h>
#define N 50010
int n,m,r[N];
struct graf
{
	int a,b;
};
graf *a[N],co[5*N];
void crmat()
{
	int i,x,c[N]={0},x1,x2,x3;
	char aux[200];
	scanf("%d%d",&n,&m);
	for(i=0; i<m; i++)
	{
		fgets(aux,200,stdin);
		scanf("%d",&x);
		c[x]++;
	}
	for(i=1; i<=n; i++)
	{
		a[i]=new graf [c[i]+5];
		a[i][0].a=a[i][0].b=0;
	}
	freopen("dijkstra.in","r",stdin);
	fgets(aux,200,stdin);
	for(i=0; i<m; i++)
	{
		scanf("%d%d%d",&x1,&x2,&x3);
		a[x1][++a[x1][0].a].a=x2;
		a[x1][a[x1][0].a].b=x3;
	}
}
void bfs()
{
	int inc=0,sf=0,i,aux;
	graf now;
	co[0].a=1;
	a[1][0].b=0;
	while(inc<=sf)
	{
		now=co[inc++];
		aux=now.a;
		if((r[now.a]==0)||(r[now.a]>now.b))
			r[now.a]=now.b;
		if(a[now.a][0].b==0)
		{
			a[now.a][0].b=1;
			for(i=1; i<=a[aux][0].a; i++)
			{
				co[++sf].a=a[aux][i].a;
				co[sf].b=now.b+a[aux][i].b;
				if((co[sf].b<r[a[aux][i].a])||(r[a[aux][i].a]==0))
					r[a[aux][i].a]=co[sf].b;
			}
		}
	}
}
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	crmat();
	bfs();
	int i;
	for(i=2; i<n; i++)
		printf("%d ",r[i]);
	printf("%d\n",r[n]);
	return 0;
}