Đổ đầy bình (Full Tank?)

Nguồn: UVa Online Judge / Kattis

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $n$ thành phố và $m$ con đường hai chiều. Giá một đơn vị nhiên liệu tại thành phố $i$ là $p_i$.

Xe tiêu thụ đúng một đơn vị nhiên liệu cho mỗi đơn vị khoảng cách và bắt đầu với bình xăng rỗng.

Mỗi truy vấn cho biết:

• dung tích bình nhiên liệu $c$;
• thành phố xuất phát $s$;
• thành phố đích $e$.

Tại một thành phố, bạn có thể mua từng đơn vị nhiên liệu với giá của thành phố đó, miễn lượng nhiên liệu trong bình không vượt quá $c$.

Hãy tìm chi phí nhiên liệu nhỏ nhất cho từng truy vấn.

Input

Dòng đầu chứa hai số nguyên $n,m$.

Dòng thứ hai chứa $n$ số nguyên $p_0,p_1,\ldots,p_{n-1}$.

Trong $m$ dòng tiếp theo, mỗi dòng chứa $u,v,d$, mô tả một con đường hai chiều giữa $u$ và $v$ có độ dài $d$.

Dòng tiếp theo chứa số truy vấn $q$.

Trong $q$ dòng cuối, mỗi dòng chứa $c,s,e$.

Các truy vấn thuộc cùng một đồ thị, vì vậy chúng vẫn nằm trong cùng một test case.

Output

Với mỗi truy vấn, in chi phí nhỏ nhất để đi từ $s$ đến $e$ với dung tích bình $c$.

Nếu không thể đi được, in impossible.

Subtask

Trong tất cả các Subtask: $0\le u,v,s,e<n$; $1\le p_i\le100$; $1\le d\le100$.

• Subtask 1 — 20% — 0.75 giây: $1\le n\le30$; $0\le m\le200$; $1\le q\le10$; $1\le c\le30$.
• Subtask 2 — 30% — 1.50 giây: $1\le n\le300$; $0\le m\le2000$; $1\le q\le50$; $1\le c\le100$.
• Subtask 3 — 50% — 3.00 giây: $1\le n\le1000$; $0\le m\le10^4$; $1\le q\le100$; $1\le c\le100$.

Ví dụ

Input

5 5
10 10 20 12 13
0 1 9
0 2 8
1 2 1
1 3 11
2 3 7
2
10 0 3
20 1 4

Output

170
impossible

Giải thích

Với truy vấn đầu, bình dung tích $10$ đủ để đi qua mạng đường và chi phí nhiên liệu nhỏ nhất là $170$. Với truy vấn thứ hai, không tồn tại hành trình từ $1$ đến $4$, nên kết quả là impossible.

##Nhãn

• Shortest Paths -> Dijkstra
• Dynamic Programming -> State compression
• Data Structures -> Priority queue