치즈버거

정후는 평소에 지하철을 자주 이용합니다. 지하철 노선도에는 지하철역 $N$개가 $M$개의 철로로 연결되어 있습니다. $i$번째 철로는 $u_i$번째 지하철역과 $v_i$번째 지하철역을 양방향으로 잇고, 이 철로를 이용하면 두 지하철역 사이를 이동하는 데 $w_i$의 시간이 걸립니다.

어느 날 정후는 한 지하철역에서 치즈버거를 먹었는데, 그 뒤로 치즈버거를 아주 좋아하게 되어 $a_1, a_2, \cdots, a_K$번째 지하철역에 치즈버거 체인점을 냈습니다. 이제 치즈를 수송해 오는 일만 남았습니다.

정후는 주변의 치즈 농장을 찾아보았고, $T$개의 치즈 농장이 $b_1, b_2, \cdots, b_T$번째 지하철역 근처에 있다는 것을 알아냈습니다. $b_i$번째 지하철역 근처 농장의 치즈 가격은 $c_i$입니다. 정후는 KTX특송으로 각 체인점에 치즈를 전달합니다. KTX특송에 걸리는 시간은 지하철역 사이를 이동하는 시간과 같습니다.

각 농장은 배송 시간이 가장 짧은 하나 이상의 체인점에 치즈를 공급할 수 있습니다. 각 체인점은 공급받을 수 있는 치즈 중 가장 싼 치즈를 구매합니다. 각 체인점이 구매하는 치즈의 가격은 얼마입니까?

첫째 줄에 네 정수 $N$, $M$, $K$, $T$가 공백으로 구분되어 주어집니다.

둘째 줄에 $K$개의 정수 $a_1, a_2, \cdots, a_K$가 공백으로 구분되어 주어집니다.

이어서 $T$개의 줄에 걸쳐 각 줄에 두 정수 $b_i$, $c_i$가 공백으로 구분되어 주어집니다.

이어서 $M$개의 줄에 걸쳐 각 줄에 세 정수 $u_i$, $v_i$, $w_i$가 공백으로 구분되어 주어집니다.

한 줄에 $i$번째 체인점이 구매하는 치즈의 가격을 나타내는 $K$개의 정수를 공백으로 구분하여 출력합니다. 체인점이 치즈를 구매할 수 없다면 -1을 출력합니다.

• $1 \leq N \leq 300\,000$
• $N-1 \leq M \leq 300\,000$
• $1 \leq K, T \leq N$
• $1 \leq a_i, b_i, u_i, v_i \leq N$
• $i<j$이면 $a_i<a_j$이고 $b_i<b_j$
• $u_i<v_i$
• $1 \leq c_i, w_i \leq 1\,000\,000\,000$