Cheeseburger

Jeonghu rides the subway often. The subway map has $N$ stations connected by $M$ rail lines. The $i$-th rail line connects stations $u_i$ and $v_i$ in both directions, and travel between those two stations takes $w_i$ time.

One day, Jeonghu ate a cheeseburger at a subway station and came to love cheeseburgers so much that he opened cheeseburger chain stores at stations $a_1, a_2, \cdots, a_K$. All that remains is to transport the cheese.

Jeonghu found $T$ cheese farms near stations $b_1, b_2, \cdots, b_T$. The cheese at the farm near station $b_i$ costs $c_i$. Jeonghu delivers cheese to each chain store by KTX express, and a KTX express delivery takes the same time as travel between stations.

Each farm can supply cheese to every chain store that has the shortest delivery time from that farm, where the shortest delivery time is taken over one or more chain stores. Each chain store buys the cheapest cheese it can be supplied with. What price does each chain store pay?

The first line contains four integers $N$, $M$, $K$, and $T$, separated by spaces.

The second line contains $K$ integers $a_1, a_2, \cdots, a_K$, separated by spaces.

The next $T$ lines each contain two integers $b_i$ and $c_i$, separated by a space.

The next $M$ lines each contain three integers $u_i$, $v_i$, and $w_i$, separated by spaces.

Print $K$ integers on one line, separated by spaces, where the $i$-th integer is the price of the cheese that the $i$-th chain store buys. If a chain store cannot buy any cheese, print -1 for it.

• $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$
• If $i<j$, then $a_i<a_j$ and $b_i<b_j$
• $u_i<v_i$
• $1 \leq c_i, w_i \leq 1\,000\,000\,000$