The way home
 The famous magician Borya Budini traveled through the country $$$X$$$, which consists of $$$n$$$ cities. However, an accident happened, and he was robbed in the city number $$$1$$$. Now Budini will have a hard way home to the city number $$$n$$$.He's going to get there by plane. In total, there are $$$m$$$ flights in the country, $$$i$$$-th flies from city $$$a_i$$$ to city $$$b_i$$$ and costs $$$s_i$$$ coins. Note that the $$$i$$$-th flight is one-way, so it can't be used to get from city $$$b_i$$$ to city $$$a_i$$$. To use it, Borya must be in the city $$$a_i$$$ and have at least $$$s_i$$$ coins (which he will spend on the flight). After the robbery, he has only $$$p$$$ coins left, but he does not despair! Being in the city $$$i$$$, he can organize performances every day, each performance will bring him $$$w_i$$$ coins. Help the magician find out if he will be able to get home, and what is the minimum number of performances he will have to organize. 
In the first example, it is optimal for Borya to make $$$4$$$ performances in the first city, having as a result $$$2 + 7 \cdot 4 = 30$$$ coins, and then walk along the route $$$1-3-2-4$$$, spending $$$6+8+11=25$$$ coins.  In the second example, it is optimal for Borya to make $$$15$$$ performances in the first city, fly to $$$3$$$ city, make $$$9$$$ performances there, and then go to $$$4$$$ city. 
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 80$$$) – the number of test cases. The description of test cases follows.The first line contains three integers $$$n$$$, $$$m$$$ and $$$p$$$ ($$$2 \le n \le 800$$$, $$$1 \le m \le 3000$$$, $$$0 \le p \le 10^9$$$) — the number of cities, the number of flights and the initial amount of coins.The second line contains $$$n$$$ integers $$$w_1, w_2, \ldots, w_n$$$ $$$(1 \le w_i \le 10^9)$$$ — profit from representations.The following $$$m$$$ lines each contain three integers $$$a_i$$$, $$$b_i$$$ and $$$s_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$1 \le s_i \le 10^9$$$) — the starting and ending city, and the cost of $$$i$$$-th flight.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$800$$$ and the sum of $$$m$$$ over all test cases does not exceed $$$10000$$$. 
For each test case print a single integer — the minimum number of performances Borya will have to organize to get home, or $$$-1$$$ if it is impossible to do this. 
import sys
R = sys.stdin.readline
S = lambda : map(int, R().split())
from collections import deque
for _ in range(int(R())):
    (n, m, p) = S()
    w = [0] + [*S()]
    e = [[] for _ in range(n + 1)]
    for _ in range(m):
        (u, v, s) = S()
        e[u] += ((s, v),)
    dd = [{} for _ in range(n + 1)]
    dd[1][w[1]] = (0, -p)
    q = deque([[w[1], 0, p, 1]])
    while q:
        (x, y, z, u) = q.popleft()
        if dd[u][x] < (y, -z):
            continue
        for (s, v) in e[u]:
            nn = [0] * 4
            nn[0] = max(x, w[v])
            if z >= s:
                nn[2] = z - s
                nn[1] = y
            else:
                nn[1] = y + (s - z + x - 1) // x
                nn[2] = z + (s - z + x - 1) // x * x - s
            nn[3] = v
            if nn[0] not in dd[v] or dd[v][nn[0]] > (nn[1], -nn[2]):
                dd[v][nn[0]] = (nn[1], -nn[2])
                q += (nn,)
    print(-1 if not dd[n] else min(dd[n].values())[0])
import sys
input = sys.stdin.readline
mod = 998244353
import heapq
from heapq import heappop, heappush

def dijkstra(adj, start):
    inf = 1 << 60
    dist = [inf] * len(adj)
    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        (min_dist, v_from) = heapq.heappop(q)
        if min_dist > dist[v_from]:
            continue
        v_tos = adj[v_from]
        for (v_to, cost) in v_tos:
            if min_dist + cost < dist[v_to]:
                dist[v_to] = min_dist + cost
                heapq.heappush(q, (dist[v_to], v_to))
    return dist
for _ in range(int(input())):
    (N, M, P) = map(int, input().split())
    W = [0] + list(map(int, input().split()))
    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        (a, b, c) = map(int, input().split())
        adj[a].append((b, c))
    dist_list = [[]]
    for v in range(1, N + 1):
        dist = dijkstra(adj, v)
        dist_list.append(dist)
    ans = 10 ** 17
    min_perf = [10 ** 17] * (N + 1)
    min_perf[1] = 0
    max_money = [0] * (N + 1)
    max_money[1] = P
    v_from = 1
    seen = [0] * (N + 1)
    for _ in range(N):
        seen[v_from] = 1
        for v_to in range(1, N + 1):
            if v_to == v_from:
                continue
            d = dist_list[v_from][v_to]
            if d == 1 << 60:
                continue
            if max_money[v_from] >= d:
                perf_new = min_perf[v_from]
                money_new = max_money[v_from] - d
            else:
                perf_num = (d - max_money[v_from] - 1) // W[v_from] + 1
                perf_new = min_perf[v_from] + perf_num
                money_new = max_money[v_from] - d + W[v_from] * perf_num
            if perf_new < min_perf[v_to]:
                min_perf[v_to] = perf_new
                max_money[v_to] = money_new
            elif perf_new == min_perf[v_to]:
                max_money[v_to] = max(max_money[v_to], money_new)
        mi = float('inf')
        v_nxt = -1
        for v_new in range(1, N + 1):
            if seen[v_new]:
                continue
            tmp = min_perf[v_new] * 10 ** 17 - max_money[v_new]
            if tmp < mi:
                mi = tmp
                v_nxt = v_new
        v_from = v_nxt
    if min_perf[N] == 10 ** 17:
        print(-1)
    else:
        print(min_perf[N])
import sys
R = sys.stdin.readline
S = lambda : map(int, R().split())
from collections import deque
for _ in range(int(R())):
    (n, m, p) = S()
    w = [0] + [*S()]
    e = [[] for _ in range(n + 1)]
    for _ in range(m):
        (u, v, s) = S()
        e[u] += ((s, v),)
    dd = [{} for _ in range(n + 1)]
    dd[1][w[1]] = (0, -p)
    q = deque([[w[1], 0, p, 1]])
    while q:
        (x, y, z, u) = q.popleft()
        if dd[u][x] < (y, -z):
            continue
        for (s, v) in e[u]:
            nn = [0] * 4
            nn[0] = max(x, w[v])
            if z >= s:
                nn[2] = z - s
                nn[1] = y
            else:
                nn[1] = y + (s - z + x - 1) // x
                nn[2] = z + (s - z + x - 1) // x * x - s
            nn[3] = v
            if nn[0] not in dd[v] or dd[v][nn[0]] > (nn[1], -nn[2]):
                dd[v][nn[0]] = (nn[1], -nn[2])
                q += (nn,)
    print(-1 if not dd[n] else min(dd[n].values())[0])