Повний бак
Після перегляду квитанцій з вашої автомобільної подорожі Європою цього літа, ви помітили, що ціни на бензин змінювалися між містами, які ви відвідали. Можливо, ви могли б заощадити трохи грошей, якби були більш обачними щодо того, де заправляти свій автомобіль.
Щоб допомогти іншим туристам (і заощадити гроші наступного разу), ви хочете створити програму, яка знайде найдешевший спосіб подорожі між містами, заправляючи бак по дорозі. Ми припускаємо, що всі автомобілі споживають одну одиницю пального на одиницю відстані і починають з порожнім баком.
Вхідні дані
Перша строка містить n (1 ≤ n ≤ 1000) та m (0 ≤ m ≤ 10000) - кількість міст та доріг. Далі йде строка з n цілими числами p_i (1 ≤ p_i ≤ 100), де p_i - це ціна пального в i-му місті. Потім йде m строк з трьома цілими числами u, v (0 ≤ u, v < n) та d (1 ≤ d ≤ 100), що вказують на наявність дороги між u та v з довжиною d. Потім йде строка з числом q (1 ≤ q ≤ 100), що вказує на кількість запитів, і q строк з трьома цілими числами c (1 ≤ c ≤ 100), s та e, де c - це ємність бака автомобіля, s - початкове місто, а e - цільове місто.
Вихідні дані
Для кожного запиту виведіть вартість найдешевшої подорожі з s до e використовуючи автомобіль з даною ємністю, або "неможливо", якщо немає способу дістатися з s до e з даним автомобілем.