时间限制：1秒　　内存限制：256M

---

【题目描述】

　　给出 \(n\) 个城市间的 \(m\) 条道路。给出起点 \(A\) 和终点 \(B\)，以及汽车的邮箱容量 \(C\)，计算 \(A\) 到 \(B\) 的最便宜路径。假定初始时邮箱为空的。第 \(i\) 个城市的油价为 \(p_i\)。需要回答 \(q\) 组询问。

【输入格式】

　　第一行为 \(n,m\)，表示城市数目和道路数目，其中城市编号为 \(1..n\)。
　　接下来的 \(n\) 行，每行一个整数 \(p_i\)，第 \(i+1\) 行的 \(p_i\) 表示第 \(i\) 个城市的油价为 \(p_i（1≤p≤100）\)。
　　再接下来的 \(m+1\) 行，每行表示一条道路 \(a,b,d\)，表示城市 \(a\) 和城市 \(b\) 之间的道路耗油量为 \(d（1≤d≤1000）\)。
　　然后一个整数\(q\)，表示询问。紧接着的 \(q\) 行，每行一个询问 \(c,s,t\)，表示询问当邮箱容量为 \(c\) 时，从城市 \(s\) 到城市 \(t\) 的最便宜路径（\(1≤c≤100\)，\(1≤s,t≤n\)）。

【输出格式】

　　每个询问输出一个整数，表示对应询问的最便宜路径，如果无法到达，输出 impossible.

【输入输出样例】

　Input

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

　Output

80
impossible

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤n≤200\)，\(1≤m≤10000\)，\(1≤q≤1000\)。

【来源】

　　Mr.he