14432번 - 우물

현성이는 너무나 따뜻한 마음씨를 가지고 있다(대회 종료 후에 사실이 아닌 것으로 확인되었다 - @behind06). 현성이는 물을 마음껏 마시지 못하는 아프리카 아이들을 위해 마을에 우물을 설치하려고 한다.

마을마다 필요한 우물의 수가 다르며, 마을 A에 우물을 하나 설치하면 마을 A와 인접한 모든 마을의 우물도 하나씩 충족된다.

예를 들어, A-B A-C 마을이 연결되어 있고, A, B, C 마을이 각각 5, 10, 7개의 우물을 필요로 할 때, A 마을에 우물을 5개 설치하면 B와 C 마을에도 우물이 5개 충족되는 셈이다.

하지만 현성이는 평소에도 기부를 워낙 많이 해서 돈이 충분하지 않다. (이것도 역시 사실이 아닌 것으로 확인되었다 - @tonyjjw)

마을의 수가 n이고, 각 마을에 필요한 최소 우물 수는 W₁, W₂, ... , W_n이고, 마을간 서로 이동할 수 있는 길의 수가 m일 때, 현성이를 위해 필요한 우물의 최소 개수를 구해주자.

첫째 줄에 마을의 개수 n(1 ≤ n ≤ 100,000)와 길의 개수 m(1 ≤ m < 100,000)개가 주어지고

둘째 줄에 각 마을에 필요한 최소 우물의 수 W₁, W₂, ... ,W_n (0 ≤ W_i ≤ 10,000,000)이 주어지고

세 번째 줄부터 m+2번째 줄까지 길의 정보가 주어진다. 길의 정보는 서로 이동할 수 있는 a마을, b마을로 이루어져 있다. 단, 임의의 마을 A에서 B까지 정확히 한 가지 경로가 존재한다.

첫째 줄에 현성이를 위해 필요한 우물의 최소 개수를 출력한다.