Туди й назад
Джим планує відвідати одного зі своїх найкращих друзів у місті, розташованому в гірській місцевості. Спочатку він вирушає зі свого рідного міста до міста призначення. Це називається фазою поїздки. Потім він повертається назад до свого рідного міста, що є фазою повернення. Ваше завдання — написати програму, яка визначить мінімальну загальну вартість цієї подорожі, що складається з вартості фази поїздки та фази повернення.
Існує мережа міст, включаючи ці два міста. Кожна дорога в цій мережі є односторонньою, тобто її можна використовувати лише в одному напрямку. Кожна дорога має певну вартість для подорожі.
Окрім вартості доріг, необхідно сплатити певну плату за проїзд через кожне місто на шляху. Однак, оскільки це візовий збір за місто, не потрібно платити плату при другому або наступних відвідуваннях того ж міста.
Кожне місто має задану висоту (висоту над рівнем моря). На фазі поїздки заборонено використовувати дороги, що ведуть вниз. Тобто, коли ви йдете з міста a до b, висота a не повинна бути більшою за висоту b. На фазі повернення заборонено використовувати дороги, що ведуть вгору, аналогічним чином. Якщо висоти a та b рівні, дорога з a до b може використовуватися на обох фазах.
Вхідні дані
Вхід складається з кількох наборів даних, кожен з яких має наступний формат.
Кожен елемент введення в наборі даних є невід'ємним цілим числом. Елементи введення в рядку розділені пробілом.
n — це кількість міст у мережі. m — це кількість (односторонніх) доріг. Ви можете припустити, що нерівності 2 ≤ n ≤ 50 та 0 ≤ m ≤ n(n-1) виконуються. Міста пронумеровані від 1 до n, включно. Місто 1 — це рідне місто Джима, а місто n — місто призначення.
d_i — це візовий збір за місто i, а e_i — його висота. Ви можете припустити 1 ≤ d_i ≤ 1000 та 1 ≤ e_i ≤ 999 для 2 ≤ i ≤ n-1. Міста 1 та n не стягують візовий збір. Висота міста 1 дорівнює 0, а висота міста n дорівнює 1000. Кілька міст можуть мати однакову висоту, але ви можете припустити, що не більше 10 міст мають однакову висоту.
j^та дорога йде з міста a_j до міста b_j з вартістю c_j (1 ≤ j ≤ m). Ви можете припустити 1 ≤ a_j ≤ n, 1 ≤ b_j ≤ n, та 1 ≤ c_j ≤ 1000. Ви можете безпосередньо перейти з a_j до b_j, але не з b_j до a_j, якщо дорога з b_j до a_j не задана окремо. Немає двох доріг, що з'єднують ту саму пару міст у тому ж напрямку, тобто для будь-яких i та j, таких що i ≠ j, a_i ≠ a_j або b_i ≠ b_j. Немає доріг, що з'єднують місто з самим собою, тобто для будь-якого j, a_j ≠ b_j.
Останній набір даних завершується рядком, що містить два нулі (розділені пробілом).
Вихідні дані
Для кожного набору даних у введенні виведіть рядок, що містить мінімальну загальну вартість, включаючи візові збори, цієї подорожі. Якщо така подорож неможлива, виведіть "-1".