#include<stdio.h>
#define N 50010
int n,m;
struct graf
{
	int a,b;
};
graf *a[N],co[5*N],r[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 repara(int k,int dif)
{
	int i;
	for(i=2; i<=n; i++)
	{
		if(r[i].a)
		{
			if(r[i].b==k)
				r[i].a-=dif;
		}
	}
}
void bfs()
{
	int inc=0,sf=0,i,aux,k;
	graf now;
	co[0].a=1;
	a[1][0].b=0;
	while(inc<=sf)
	{
		now=co[inc++];
		aux=now.a;
		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].a)||(r[a[aux][i].a].a==0))
				{
					k=r[a[aux][i].a].a;
					r[a[aux][i].a].a=co[sf].b;
					r[a[aux][i].a].b=aux;
					repara(a[aux][i].a,k-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].a);
	printf("%d\n",r[n].a);
	return 0;
}