+ محدودیت زمان: ۱.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + منبع: آزمون نهایی دوم دوره ۲۷ المپیاد کامپیوتر ---------- وحید مدیرعامل مجموعه توریستی «بی‌آبان» در کویر لوط است. مهیج‌ترین بازی این مجموعه، لیز خوردن از تپه‌های شنی است. در این مجموعه $n$ تپه شنی وجود دارد که از $0$ تا $n-1$ شماره‌گذاری شده‌اند. ارتفاع تپه‌ی $i$، $h_i$ است. $m$ راه شنی تپه‌ها را به هم متصل می‌کند، راه $i$، تپه $v_i$ و $u_i$ را به یکدیگر متصل می‌کند. می‌توان از تپه $i$ به تپه $j$ لیز خورد، اگر بین این دو تپه راه شنی وجود داشته باشد و $h_j \le h_i$. وحید می‌خواهد در مجموعه‌اش بتوان از تپه $0$ شروع کرد و با لیز خوردن به تپه $n-1$ رسید. برای اینکار او می‌تواند ارتفاع تپه‌ها را تغییر دهد، برای تغییر ارتفاع تپه‌ای از $x$ به $y$ باید $|x-y|$ هزینه کند. او حق پدری بر گردن کامپیوتری‌ها دارد، به او کمک کنید و کمترین هزینه برای اینکه او به خواسته‌اش برسد را بگویید. # ورودی در سطر اول ورودی، دو عدد $n$ و $m$ آمده‌است. در سطر دوم، $n$ عدد $h_0, h_1, \dots, h_{n-1}$ آمده‌است. سپس در $i$ امین سطر از $m$ سطر بعدی، دو عدد $v_i$ و $u_i$ آمده‌است. $$1 \le n, m \le 1\ 000$$ $$0 \le h_i \le 10^9$$ $$0 \le v_i, u_i < n$$ # خروجی در تنها سطر خروجی، کمترین هزینه برای رسیدن وحید به خواسته‌اش را چاپ کنید. اگر چنین کاری ممکن نبود، $-1$ چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت | |:-------:|:----------:|:-----------:| |۱ | ۸ | $n \le 5$| |۲| ۲۱ | گراف داده شده درخت است. | |۳| ۲۸ |$n \le 100$ | |۴| ۴۳ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 3 2 30 20 10 0 1 1 2 ``` ## خروجی نمونه ۱ ``` 0 ``` ## ورودی نمونه ۲ ``` 2 1 10 20 0 1 ``` ## خروجی نمونه ۲ ``` 10 ``` ## ورودی نمونه ۳ ``` 3 1 1396 1396 1396 0 1 ``` ## خروجی نمونه ۳ ``` -1 ```