30102번 - 치즈버거

문제

정후는 평소에 지하철을 자주 이용합니다. 지하철 노선도에는 지하철역 $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円$

힌트