K. Going to Find Your Love
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

我们可以把东南大学的校园抽象成一个$$$n$$$个点，$$$m$$$条边的有向图，每条边有长度$$$w$$$。

在校园中有$$$p$$$个点上有障碍物，你最多可以搬走$$$k$$$个障碍物，即你最多经过$$$k$$$个有障碍物的点。

那么，现在请问，在最多可以搬走$$$k$$$个障碍物的条件下，你从点$$$1$$$出发，到其他点的最短距离分别为多少。

Input

第一行，$$$4$$$个整数 $$$n,m,p,k(1\le n \le 10^5;0\le m \le \min(10^5,n·(n-1));0\le p \le n-1;0\le k \le 5)$$$，分别代表图中的点数、边数、有障碍物的点数和你最多搬走的障碍物数量。

第二行，有$$$p$$$个整数，代表有障碍物的点的下标，保证这$$$p$$$个整数互不相同，且点$$$1$$$没有障碍物。

接下来连续的$$$m$$$行，每行$$$3$$$个整数 $$$u,v,w(1\le u,v \le n;1\le w \le 10^9)$$$，代表一条有向边的起点、终点和边的长度。

保证最终给定的图无重边、无自环。

Output

在一行中输出用空格隔开的$$$n$$$个整数，代表从点$$$1$$$出发到达$$$n$$$个点的最短距离，如果不能到达某一个点，那就输出'-1'。

Example
Input
6 6 3 2
4 5 6
5 6 1
1 2 1
1 3 2
2 4 1
3 4 2
4 5 4
Output
0 1 2 2 6 -1