행성 간 여행

2306년, 나노기술의 발전으로 행성 간 여행이 보편화되고 있다. 비비카는 우주에서 가장 큰 행성 간 여행사에서 일하며, 매일 여행을 원하는 고객을 맞이한다.

비비카의 고객은 까다로워서 여행 경로를 확정하기 전에 여러 조건을 내건다. 대표적으로 이동 거리의 합을 최소화하는 것이다. 그러나 가장 큰 제약은 경로에서 방문하는 행성(출발 행성과 도착 행성은 제외)의 온도에 대한 것이다. 행성의 온도는 아니다도(Anidos) 단위로 측정하며, -10^9 아니다도부터 +10^9 아니다도까지의 값을 가질 수 있다. 비비카의 고객은 기후가 다양한 행성에서 오기 때문에 온도 선호도가 서로 다르다. 어떤 고객은 매우 추운 행성을 걱정하고, 어떤 고객은 매우 더운 행성을 걱정한다. 비비카는 총 이동 거리가 최소가 아니더라도(심지어 경로가 아예 없더라도, 이 경우 비비카는 여행이 불가능하다고 고객에게 알린다) 고객이 불편을 겪지 않도록 여행 경로를 계획해야 한다.

비비카는 N개의 행성 각각의 역사적 평균 기온과, 행성 쌍을 직접 연결하는 R개의 노선(두 행성 사이에 직접 노선은 최대 하나뿐임이 보장된다) 및 각 노선의 거리를 알려 주었다. 또한 Q명의 고객이 보낸 여행 요청도 알려 주었다. 각 여행 요청은 출발 행성 A, 도착 행성 B, 그리고 중간 행성의 온도에 대한 고객의 제한으로 이루어진다. 각 고객은 전체 N개 행성 중 온도가 가장 낮은 K개 또는 가장 높은 K개에 속하는 행성만 이용하도록 요구할 수 있다.

여러분의 과제는 각 여행 요청에 대해 주어진 제한 아래에서 가능한 최단 거리를 구하거나, 그러한 여행이 불가능하다고 판정하는 것이다.

입력의 첫째 줄에는 두 정수 N과 R(2 ≤ N ≤ 400, 0 ≤ R ≤ N·(N-1)/2)이 주어진다. 이는 알려진 행성의 수와 행성 사이의 직접 노선의 수를 나타낸다. 첫 번째 행성은 1, 두 번째 행성은 2, ..., N번째 행성은 N으로 나타낸다. 입력의 둘째 줄에는 N개의 정수 T_i(-10^9 ≤ T_i ≤ 10^9)가 주어지며, 이는 각 행성의 평균 기온을 나타낸다. 그다음 R개의 줄이 주어지며, 각 줄에는 세 정수 X, Y, D(1 ≤ X, Y ≤ N, X ≠ Y, 1 ≤ D ≤ 10^3)가 주어진다. 이는 행성 X와 Y 사이에 길이 D인 직접 노선이 있음을 나타낸다. 그다음 정수 Q(1 ≤ Q ≤ 10^5)가 주어지며, 이는 고객 여행 주문의 수를 나타낸다. 마지막으로 다음 Q개의 줄 각각에는 네 정수 A, B, K, T(1 ≤ A, B, K ≤ N, A ≠ B, T ∈ {0, 1})가 주어진다. 이는 T = 0이면 온도가 가장 낮은 K개에 속하는 행성만, T = 1이면 온도가 가장 높은 K개에 속하는 행성만 거쳐서 행성 A에서 행성 B로 가려는 고객을 나타낸다.

각 고객 요청마다 한 줄을 출력한다. 고객의 제한 아래에서 두 행성 사이의 최단 총 이동 거리를 정수로 출력하거나, 여행이 불가능하면 -1을 출력한다.