IK-WARM Virus

Oh Ik-jun, a hacker in the 영과일 organization, plans to infect a PC with his newly developed virus 'IK-WARM' and then have the virus spread to every PC on the network.

The network has $N$ PCs and $M$ network edges, forming an undirected graph. Each edge has a unique transmission time, which is the time needed to send data between the two PCs it connects. The two PCs in each transmission are different, and any two PCs have at most one direct connection.

A PC infected with the virus can send data containing the virus to its neighbors through the network edges, and a PC that receives such data is infected immediately.

Oh Ik-jun can hack up to $K$ different PCs and send data containing the virus to them directly. The time needed to send data to PC $i$ is $a_i$.

Given the sequence $a$ and the network information, find the minimum total transmission time needed to infect every PC in the network that has no infected PC at the start. Here, the total transmission time is the sum of the times spent sending data to each PC.

The first line contains three integers $N$, $M$, and $K$, the number of PCs, the number of edges, and the maximum number of direct transmissions. $(1 \leq N \leq 1\,000;\ 0 \leq M \leq \min(\frac{N(N-1)}{2},\ 100\,000);\ 1 \leq K \leq N)$

The second line contains $N$ integers $a_i$, separated by spaces, the time needed to send virus-containing data to each PC. $(1 \leq a_i \leq 100\,000;\ 1 \leq i \leq N)$

Each of the next $M$ lines contains three integers $X$, $Y$, and $Z$, separated by spaces. This means PC $X$ and PC $Y$ are connected by an edge with transmission time $Z$. $(1 \leq X, Y \leq N;\ 1 \leq Z \leq 100\,000)$

Print the minimum total transmission time needed to infect every PC on the network on the first line. If the virus cannot spread to the entire network, print -1.