Полный бак
После анализа чеков с вашей автомобильной поездки по Европе этим летом, вы заметили, что цены на бензин варьировались в разных городах, которые вы посетили. Возможно, вы могли бы сэкономить, если бы более тщательно выбирали места для заправки.
Чтобы помочь другим путешественникам (и сэкономить в следующий раз), вы хотите разработать программу, которая найдет самый дешевый способ путешествия между городами, заправляя бак по пути. Мы предполагаем, что все автомобили расходуют одну единицу топлива на единицу расстояния и начинают с пустым баком.
Входные данные
Первая строка содержит 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 с использованием автомобиля с заданной вместимостью, или impossible, если нет способа добраться из s в e с данным автомобилем.