Cırtdanlar qülləsi

Kiçik Vasya "Cırtdanların Qülləsi" oyununu oynayır. Bu oyunda sizin personajınıza — cırtdana geyindirmək üçün $n$ fərqli əşya mövcuddur. Əşyalar $1$-dən $n$-ə qədər nömrələnib. Vasya $1$ nömrəli əşyanı əldə etmək istəyir.

Əşyaları əldə etməyin iki yolu var:

• Siz əşyanı ala bilərsiniz. $i$-ci əşya $c_i$ pul dəyərindədir.

• Siz əşyanı qura bilərsiniz. Oyunda yalnız $m$ fərqli qurma variantı mövcuddur. Yeni əşya əldə etmək üçün iki fərqli əşya vermək lazımdır.

Vasyaya $1$ nömrəli əşyanı əldə etmək üçün ən az pul xərcləməyə kömək edin.

Giriş verilənləri

Birinci sətir iki ədəd $n$ və $m(1\le n\le 10^4,0\le m\le 10^5)$ — fərqli əşyaların sayı və qurma variantlarının sayını ehtiva edir.

İkinci sətir $n$ tam ədəd $c_i(0\le c_i\le 10^9)$ — əşyaların qiymətlərini ehtiva edir.

Növbəti $m$ sətir əşyaların çevrilməsini təsvir edir, hər sətir üç fərqli tam ədəd $a_i,x_i,y_i$ ehtiva edir, burada $a_i$ — $x_i$ və $y_i$-dən qurula bilən əşyadır $(1\le a_i,x_i,y_i\le n,a_i\ne x_i,x_i\ne y_i,y_i\ne a_i)$.

Çıxış verilənləri

Bir ədəd çıxarın — xərclənən ən az pul miqdarı.

Nümunələr