Хүүхдүүдийн өдрөөр хүүхэд Делэеийн бэлэгнээс тоглоом авсан. Гэвч хүүхэд үнэхээр дэггүй учраас тоглоомоо эвдэхийг тэсэж ядан хүлээж байв.

Тоглоом нь $n$ хэсэг болон $m$ холбоосноос бүрддэг. Холбоос бүр нь хоёр хэсгийг холбодог, гэвч хэсгүүдийн хос бүр хамгийн багадаа нэг холбоосоор холбогдсон. Хүүхэд тоглоомыг хуваахын тулд бүх хэсгүүдийг авч хаях ёстой. Хүүхэд цагт нэг хэсгийг авч хаяж чадах ба авч хаях бүртээ энерги шатаана. $i$-р хэсгийн энергийн утгыг $v_{i}$ гэж тодорхойлцгооё. $f_{1}, f_{2}, ..., f_{k}$ хэсгүүдтэй $i$-р хэсэг шууд холбогдсон ба авч хаяагүй бол $i$-р хэсгийг хаяхад $v_{f_{1}} + v_{f_{2}} + ... + v_{f_{k}}$ энерги зарцуулна.

Бүх $n$ хэсгүүдийг авч хаяхад хамгийн багадаа зарцуулах энергийг олоход нь тусал.

Оролт

Эхний мөр нь $n$, $m$ ($1 ≤ n ≤ 1000$; $0 ≤ m ≤ 2000$) хоёр бүхэл тоог агуулна. Хоёр дахь мөр нь $n$ бүхэл тоонуудыг агуулна: $v_{1}, v_{2}, ..., v_{n}$ ($0 ≤ v_{i} ≤ 10^{5}$). Дараа нь $m$ мөр байх ба мөр бүр $x_{i}$ ба $y_{i}$ хоёр хэсгийг агуулна, энэ нь $x_{i}$ хэсгээс $y_{i}$ хэсэгрүү холбоосыг илэрхийлнэ ($1 ≤ x_{i}, y_{i} ≤ n; x_{i} ≠ y_{i}$).

Бүх хэсгүүд нь $1$-с $n$ хүртэл дугаарлагдана.

Гаралт

Хүүхэд тоглоомын бүх $n$ хэсгүүдийг авч хаяхад зарцуулах энергийн хамгийн бага хэмжээг хэвлэнэ.

Эхний жишээнд үйлдлийн оновчтой дараалал нэг байна:

• Эхлээд, $3$-р хэсгийг авч хаяна, үйлдэлд зарцуулах энерги нь $20$.
• Дараа нь $2$-р хэсгийг авч хаяна, cost of the action is $10$.
• Дараа нь $4$-р хэсгийг авч хаяна, үйлдэлд зарцуулах энерги нь $10$.
• Хамгийн сүүлд $1$-р хэсгийг авч хаяна, үйлдэлд зарцуулах энерги нь $0$.

Тэгэхээр хүүхэд хамгийн багадаа $20 + 10 + 10 + 0 = 40$ энерги зарцууулна.

Хоёр дахь жишээнд ямар ч хамаагүй байдлаар авч хаяхад $400$ энерги зарцууулна.