Cırtdanların Qalası#6263
Balaca Vəsya "Cırtdanların Qalası" adlanan oyunu oynayır. Bu oyunda cırtdan adlı personaj üzərinə geyiləcək müxtəlif əşya var. Bütün əşyalar -dən -ə qədər nömrələnib. Vəsya nömrəli əşyanı əldə etmək istəyir.
Əşyaları əldə etməyin iki yolu var:
Əşya almaq: -ci əşya c_i pul tutur.
Əşya yığmaq: oyunda müxtəlif resept mövcuddur. Yeni əşya yığmaq üçün iki fərqli əşya vermək lazımdır.
Vəsyaya ən az pul xərcləməklə nömrəli əşyanı əldə etməyə kömək edin.
Birinci sətir və (1 \le n \le 10^4, 0 \le m \le 10^5) iki ədədini verir — fərqli əşyaların sayı və yığma reseptlərinin sayı.
İkinci sətir tam ədəd c_i (0 \le c_i \le 10^9) verir — əşyaların qiyməti.
Növbəti sətirin hər biri bir resepti təsvir edir. Hər sətir üç fərqli tam ədəd a_i, x_i, y_i verir, burada a_i əşyası x_i və y_i əşyalarından yığılı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).
Bir ədəd çıxarın — xərclənməli minimum pul miqdarı.
Nümunə 1
Nümunə 2