有 \(n\) 個小村鎮以 \(1 \sim n\) 編號，這些村鎮以 \(n - 1\) 條道路連接，每條道路都是雙向通行且連接兩個不同的村鎮。
已知從任意兩個村莊之間都可以經由這些道路通達。兩個村莊稱為鄰近的村莊，如果它們之間有一條道路直接相連。

現在要選一些村莊成立服務中心。因為預算的關係，無法每個村莊都成立一個服務中心。政府的政策決定：

• 如果某個村莊沒有設服務中心，那麼一定要有一個鄰近的村莊設有服務中心。
• 也就是說，任何一個村莊最多只需要經過一條道路就可以到達一個有設服務中心的村莊。

每個村莊設立服務中心的成本不同。在編號 \(i\) 的村莊成立服務中心需要的成本是 \(w[i]\)。 我們希望以最少的總成本設置服務中心，請計算最少的總成本。

輸入格式

第一行是一個正整數 \(n\)，表示村莊的數量，且 \(n > 1\)。村莊依序以 \(1 \sim n\) 編號。

第二行包含 \(n\) 個正整數，依序為 \(w[1], w[2], \dots, w[n]\)，表示在每個村莊設立服務中心的成本。

接下來有 \(n - 1\) 行，每一行包含兩個正整數 \(u\) 與 \(v\)，代表有一條道路連接村莊 \(u\) 與村莊 \(v\)。

• \(n \leq 10^5\)
• 每個村莊設置成本不超過 \(1000\)。

輸出格式

最少的總成本

範例輸入 1

5
2 4 1 3 7
1 2
5 1
5 3
5 4

範例輸出 1

6

範例輸入 2

7
1 3 3 1 2 2 1
1 2
2 3
4 3
5 4
5 6
7 6

範例輸出 2

3