Круговой маршрут
Джим планирует навестить одного из своих лучших друзей в городе, расположенном в горной местности. Сначала он отправляется из своего родного города в город назначения, что называется фазой отправления. Затем он возвращается обратно в свой родной город, что называется фазой возвращения. Ваша задача — написать программу, которая определит минимальную общую стоимость этой поездки, включая затраты на обе фазы.
Существует сеть городов, включая два указанных города. Каждая дорога в этой сети односторонняя, то есть движение возможно только в одном направлении. Каждая дорога имеет определенные затраты на проезд.
Кроме затрат на дороги, необходимо оплатить визовый сбор за проезд через каждый город на пути. Однако, так как это визовый сбор за город, его не нужно платить при втором или последующем посещении того же города.
У каждого города задана высота (над уровнем моря). На фазе отправления запрещено использовать дороги, ведущие вниз по высоте. То есть, при движении из города 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). Вы можете напрямую перейти из 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".