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

Description

    RPK和 MSH终于来到了神秘花园！

    MSH：“那儿好美啊，我们过去看看吧！”

    于是虽然在路上有着许多看不见得危险，RPK依旧带着MSH，穿越这些危险，去寻找只属于他们的美丽风景。花园由N个小岛组成，小岛间有M座桥相连接。每个小岛都有一个危险程度，每座桥都有一个通过的时间。

    现在RPK和MSH在i小岛上，美丽的景色出现在j小岛上，RPK因为有佳人在身旁，因此为了看到那美丽的景色，最多他只能冒险经过危险程度为k的小岛，同时MSH希望他们能用最少的时间到达风景所在地。在看完一处景色后，他们会被一种神奇的力量带到另外一座小岛，同时原先的景色也会消失，一处新的景色又会渐渐浮现。

    RPK带着MSH看完了所有的风景，之后把MSH安全的送回了家。

    MSH永远也不会忘记这次美妙的约会！

Input Format

    第一行2个数，N和M分别表示小岛和桥的数量。

    第二行N个数，表示每座小岛的危险程度D_n。

    接下来M行，每行3个数x，y，len，表示从x到y有一座花时len的桥。

    第M+3行，一个整数Q，表示会出现多少个风景。

    接下来Q行，每行3个数i，j，k表示当前在i，风景在j，最大冒险为k。

Output Format

    输出一共Q行，每行一个数表示花费的最少时间，如果无法到达，则输出-1。

4 4
    100 2 3 100
    0 1 1
    0 2 1
    1 3 2
    2 3 3
    2
    0 3 2
    0 3 1

3
    -1

Hint

【数据规模】

    100%的数据

    N≤200

    Dn≤1000,000,000

    len≤1000

    Q≤100000

    K≤1000,000,000