你是一間網路科技公司的專案規劃負責人，目前公司要你提出一個專案規劃來競爭一個新興國家的網路服務採購標案。

案子的內容其實很單純，該國家要把境內共 $N$ 個城市(編號 $1 - N$)都連上國家高速網路（就是把 $N$ 個城市都連在一起），並希望壓低成本，把每一分錢都用在刀口上。

目前你帶領的部屬已經評估出 $M$ 條可行的施工路線(編號 $1 - M$)，每條路線連接兩個城市並有對應的建設成本。

然而，有 $K$ 條路線為「必要路線」—— 由於地形限制，這些路線無論如何都必須建設。 在所有必要路線都需建設的前提下，請問至少要花費多少成本，才能讓所有城市都連通？

若遇到以下兩種狀況，要特別處理。

若必要路線本身已造成環（cycle），或無論如何都無法讓所有城市連通，請輸出 -1。

子任務說明

子任務1：
範例測資

子任務2：
$2 \le N \le 10$
$1 \le M \le 20$
$ K = 0 $
不會有環或無法讓所有城市連通狀況

子任務3：
$2 \le N \le 10$
$1 \le M \le 20$
$0 \le K \le M$
不會有環或無法讓所有城市連通狀況

子任務4：
$2 \le N \le 1,000$
$1 \le M \le 5,000$
$ K = 0 $
不會有環或無法讓所有城市連通狀況

子任務5：
$2 \le N \le 1,000$
$1 \le M \le 5,000$
$0 \le K \le M$
不會有環或無法讓所有城市連通狀況

子任務6：
$2 \le N \le 1,000$
$1 \le M \le 5,000$
$0 \le K \le M$

子任務7：
沒有題目敘述(含輸入格式 Input Format 說明)之外的限制