관광 안내소

바이트땅의 왕 비타사르는 아름다운 경치가 가득한 자기 나라에 관광객이 몰려와 돈을 쓰고, 그 돈이 결국 왕실 금고로 들어오기를 바란다. 그러나 현실은 왕의 꿈과 다르다. 왕이 신하에게 원인을 알아보라고 시키자, 신하는 도로망이 성글어서 외국인이 바이트땅을 찾지 않는다는 사실을 알아냈다.

바이트땅에는 도시가 $n$개 있고, 서로 다른 두 도시를 잇는 양방향 도로가 $m$개 있다. 도로는 고가도로나 터널을 지나기도 한다. 모든 도시가 서로 오갈 수 있다는 보장은 없다.

신하는 지금의 도로망으로는 긴 여행을 할 수 없다는 점도 확인했다. 어느 도시에서 출발하든, 같은 도시를 두 번 지나지 않고 도시를 10개보다 많이 방문할 수는 없다.

금고 사정이 넉넉하지 않아 새 도로는 놓지 않는다. 대신 비타사르는 관광 안내소를 세우고 직원을 두어 짧은 여행 상품을 홍보하기로 했다. 모든 도시에 대해, 그 도시 자신이나 도로로 직접 이어진 도시 중 적어도 한 곳에 관광 안내소가 있어야 한다. 관광 안내소를 세우는 비용은 도시마다 정해져 있다. 이 조건을 만족하면서 관광 안내소를 세우는 가장 싼 방법을 찾아라.

첫째 줄에 도시의 수 $n$과 도로의 수 $m$이 공백 하나를 사이에 두고 주어진다 ($2 \le n \le 20000$, $0 \le m \le 25000$). 도시에는 1번부터 $n$번까지 번호가 붙어 있다.

둘째 줄에 $n$개의 정수 $c_1, c_2, \dots, c_n$이 공백 하나씩을 사이에 두고 주어진다 ($0 \le c_i \le 10000$). $c_i$는 $i$번 도시에 관광 안내소를 세우는 비용이다.

다음 $m$개의 줄에는 도로가 하나씩 주어진다. 그중 $i$번째 줄에는 두 정수 $a_i$, $b_i$가 공백 하나를 사이에 두고 주어지며 ($1 \le a_i < b_i \le n$), $a_i$번 도시와 $b_i$번 도시가 도로로 이어져 있다는 뜻이다. 두 도시를 직접 잇는 도로는 많아야 하나다.

전체 배점의 20%에 해당하는 데이터에서는 $n \le 20$이다.

관광 안내소를 모두 세우는 데 드는 비용의 합을 한 줄에 출력한다.

첫 번째 예제에서는 1번, 5번, 6번 도시에 관광 안내소를 세우는 것이 가장 싸고, 비용은 $3+2+2=7$이다.