当前没有测试数据。

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

妖梦与麻薯

题目背景

“妖梦张口闭口都是‘那是什么？’、‘这是什么意思？’，连这里那些不能说话的幽灵都忍不住要暗示你了。”

“非常抱歉，可是，所谓‘下问则耻一时，不问则耻一世’。”

“呵呵呵，妖梦啊，你在提问是感到过一时之耻吗？”

“哎？”

“只有你提问的东西是理应知道而你却不知道的情况下，向他人询问才会感到羞耻。这种问题有多少就该问多少，不懂装懂可是要吃大亏的。”

“……”

“可是，如果只是出于你想知道而提问，并不会感到羞耻。无法感受到任何羞耻心的提问，未必一定能得到答案。自己想知道的事情就该自己动脑筋思考。如果身处一个想知道什么都能从他人口中得到答案的环境中，日子一久你的求知欲和探索欲便会被逐渐磨平。没有求知欲的人生，只能称其为不幸。没错……尤其是寿命还很长的人生”

——《东方梦月抄》

题目描述

妖梦在受到幽幽子的教导后受益很深，决定自己去图书馆研究制造去往月球的火箭的方法。可是路很远，小小的妖梦很容易饿，不吃麻薯她会走不动路。

她发现幻想乡世界有$N$家饭店卖麻薯，为了避免受到第二次月面战争的影响，妖梦和图书馆老板会进行$T$次搬迁，第$t$次他们分别搬迁到第$S_t$和第$E_t$个饭店里，也就是说，妖梦可以在家和图书馆买到麻薯。这些饭店之间有$M$条能来回走动的道路连接，第$i$家饭店的麻薯售价是每个$val_i$元，走过第$k$条道路妖梦要吃掉$W_k$个麻薯。要是妖梦身上带的麻薯小于$W_k$个，她就会害怕半路饿得走不动而不想走这条路。

小小的妖梦力气太小，她最多只能同时携带$C$个麻薯。

你看着妖梦好可怜，可惜不能到幻想乡去帮她背麻薯，于是你决定让她少花一些钱。请你帮她算出每次搬迁后从家到图书馆最少要花多少钱，或者告诉妖梦这是不可能的。

输入格式

第一行五个正整数$N,M,C$，依次表示饭店的数量，这些饭店间的道路数量

接下来一行$N$个正整数，第$i$个数$val_i$表示第$i$家饭店的麻薯单价

接下来$M$行，第$i+2$行三个正整数$f_i,g_i,W_i$，表示一条连接饭店$f_i,g_i$的道路

接下来一行一个正整数$T$，表示妖梦和图书馆老板会搬迁$T$次

接下来$T$行，每行两个正整数$S,E$，表示妖梦会搬迁到饭店$S$，图书馆老板会搬到饭店$E$里

输出格式

对于每次搬迁，如果妖梦可以从家走到图书馆，输出一行一个正整数表示妖梦从家到图书馆的最小花费；否则输出一行impossible

样例 #1

样例输入 #1

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

样例输出 #1

170

提示

样例输入2,3:

见选手附件下的 youmu2.in\youmu2.ans 和 youmu3.in\youmu3.ans

数据范围

特殊性质A：所有道路费用之和不大于$C$ 特殊性质B：所有饭店按顺序$1\sim N$排列在一条直线上，即对于所有$1\leq k < N$，都有且只有一条边$Edge(k,k+1)$连接第$k$个和第$k+1$家饭店，且保证$S<E$

题目背景by FOX_konata