익웜 바이러스

영과일 조직의 해커 오익준은 새로 개발한 바이러스 'IK-WARM'을 PC에 전송해 감염시킨 뒤, 이 바이러스가 네트워크의 모든 PC에 퍼지기를 바란다.

네트워크에는 PC가 $N$대 있고, PC 사이의 데이터 전송에 걸리는 고유한 시간을 가진 네트워크 간선이 $M$개 있는 양방향 그래프이다. 데이터를 주고받는 두 PC는 서로 다르며, 두 PC를 직접 잇는 데이터 전송 경로는 최대 한 개이다.

감염된 PC는 인접한 네트워크 간선을 통해 바이러스가 포함된 데이터를 보낼 수 있고, 바이러스가 포함된 데이터를 받은 PC는 즉시 감염된다.

오익준은 서로 다른 PC를 최대 $K$번 해킹해서 바이러스가 포함된 데이터를 직접 보낼 수 있다. $i$번 PC에 데이터를 보내는 데 걸리는 시간은 $a_i$이다.

수열 $a$와 네트워크 정보가 주어졌을 때, 처음에 감염된 PC가 하나도 없는 네트워크의 모든 PC가 감염되는 데 필요한 총 전송 시간의 최솟값을 구하라. 여기서 총 전송 시간은 각 PC에 데이터를 보내는 데 걸린 시간을 모두 더한 값이다.

첫 줄에 PC의 수 $N$, 간선의 개수 $M$, PC를 직접 해킹해 데이터를 보낼 수 있는 횟수 $K$가 공백으로 구분되어 주어진다. $(1 \leq N \leq 1\,000;\ 0 \leq M \leq \min(\frac{N(N-1)}{2},\ 100\,000);\ 1 \leq K \leq N)$

둘째 줄에는 바이러스가 포함된 데이터를 보내는 데 걸리는 시간 $a_i$가 공백으로 구분되어 $N$개 주어진다. $(1 \leq a_i \leq 100\,000;\ 1 \leq i \leq N)$

다음 $M$개의 줄에는 각 네트워크 간선의 정보를 나타내는 세 정수 $X$, $Y$, $Z$가 공백으로 구분되어 주어진다. 이는 $X$번 PC와 $Y$번 PC가 데이터를 보내는 데 $Z$의 시간이 걸리는 간선으로 연결되어 있다는 뜻이다. $(1 \leq X, Y \leq N;\ 1 \leq Z \leq 100\,000)$

첫 줄에 네트워크의 모든 PC가 감염되는 데 필요한 총 전송 시간의 최솟값을 출력한다. 바이러스가 네트워크 전체에 퍼질 수 없다면 -1을 출력한다.