치즈버거

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