Interplanetary

It is the year 2306, and with the advancement of nanotechnology, interplanetary travel is becoming generally available. Bibika works at the largest interplanetary travel agency in the universe and receives interested clients every day.

Bibika's customers are demanding and impose several constraints before closing their travel itinerary, such as minimizing the total distance traveled. But the biggest constraints concern the temperatures of the planets visited on the route (excluding the source and destination planets). The temperature of a planet, measured in degrees Anidos, can range from 10^9 negative degrees Anidos to 10^9 positive degrees Anidos. Bibika's clients come from planets of varying climates and therefore have different temperature preferences: some worry about very cold planets and others about very hot planets. Bibika must plan the travel route so as to spare the customer any discomfort, even if the total length of the route is not as short as possible (or even if there is no route at all, in which case Bibika simply informs the customer that the trip is impossible).

Bibika has provided you with the historical average temperature of each of the N planets and the R routes that connect pairs of planets directly (it is guaranteed that between two planets there is at most one direct route), along with their respective distances. She has also provided you with travel requests from Q customers. Each travel request consists of a source planet A, a destination planet B, and the customer's restriction on intermediate planet temperatures: each customer may require only planets whose temperatures are among the lowest K or the highest K among all N planets.

Your task is, for each travel request, to find the shortest possible distance under the restrictions described, or to say that such travel is impossible.

The first line of input contains two integers N and R (2 ≤ N ≤ 400 and 0 ≤ R ≤ N·(N-1)/2), which represent the number of known planets and the number of direct routes between them. The first planet is represented by the number 1, the second by the number 2, ..., up to the N-th represented by the number N. The second line of input contains N integers T_i (-10^9 ≤ T_i ≤ 10^9), which represent the average temperature of each of the planets. Then there will be R lines, each with three integers X, Y and D (1 ≤ X, Y ≤ N where X ≠ Y and 1 ≤ D ≤ 10^3), which represent a direct route of length D between planets X and Y. Then there will be an integer Q (1 ≤ Q ≤ 10^5), which represents the number of customer travel orders. Finally, each of the following Q lines will contain four integers A, B, K and T (1 ≤ A, B, K ≤ N with A ≠ B and T ∈ {0, 1}), which represent a customer who wants to go from planet A to planet B going only through planets whose temperatures are among the coldest K temperatures if T = 0 or the hottest K temperatures if T = 1.

Your program must print one line per customer request, containing an integer representing the shortest total travel distance between the two planets under the customer's restrictions, or -1 if the trip is impossible.