32650번 - 익웜 바이러스

문제

영과일 조직의 해커 오익준은 새로 개발한 바이러스 'IK-WARM'을 PC에 전송하여 감염시킨 후, 바이러스들이 네트워크상에 모두 퍼지길 원한다.

네트워크에는 $N$개의 PC가 있고, PC간 데이터를 보내는 데까지 걸리는 고유한 시간이 포함된 $M$개의 네트워크 간선으로 이루어진 양방향 그래프이다. 데이터를 송수신하는 두 PC는 서로 다르며, 두 대간 직접 연결되어 있는 데이터 전송 경로는 최대 한 개이다.

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

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

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

입력

첫 번째 줄에 PC의 수 $N,ドル PC간 간선의 개수 $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을 출력한다.

제한

힌트