Повний бак#6221

Повний бак

1 секунда

64 мегабайти

Складна

Після перегляду квитанцій з вашої автомобільної подорожі Європою цього літа, ви помітили, що ціни на бензин змінювалися між містами, які ви відвідали. Можливо, ви могли б заощадити трохи грошей, якби були більш обачними щодо того, де заправляти свій автомобіль.

Щоб допомогти іншим туристам (і заощадити гроші наступного разу), ви хочете створити програму, яка знайде найдешевший спосіб подорожі між містами, заправляючи бак по дорозі. Ми припускаємо, що всі автомобілі споживають одну одиницю пального на одиницю відстані і починають з порожнім баком.

Вхідні дані

Перший рядок містить $n$ ( $1 \leq n \leq 1000$ 1 \leq n \leq 1000) та $m$ ( $0 \leq m \leq 10000$ 0 \leq m \leq 10000) - кількість міст та доріг. Далі йде рядок з $n$ цілими числами $p_{i}$ p_i ( $1 \leq p_{i} \leq 100$ 1 \leq p_i \leq 100), де $p_{i}$ p_i - це ціна пального в $i$ -му місті. Потім йде $m$ рядків з трьома цілими числами $u$ , $v$ ( $0 \leq u, v < n$ 0 \leq u, v < n) та $d$ ( $1 \leq d \leq 100$ 1 \leq d \leq 100), що вказують на наявність дороги між $u$ та $v$ з довжиною $d$ . Потім йде рядок з числом $q$ ( $1 \leq q \leq 100$ 1 \leq q \leq 100), що вказує на кількість запитів, і $q$ рядків з трьома цілими числами $c$ ( $1 \leq c \leq 100$ 1 \leq c \leq 100), $s$ та $e$ , де $c$ - це ємність бака автомобіля, $s$ - початкове місто, а $e$ - цільове місто.

Вихідні дані

Для кожного запиту виведіть вартість найдешевшої подорожі з $s$ до $e$ використовуючи автомобіль з даною ємністю, або impossible, якщо немає способу дістатися з $s$ до $e$ з даним автомобілем.

Приклади

Приклад 1