### 问题描述 小怂是一个忠实的原友。有一天他像往常一样原，突然电闪雷鸣，他穿越到了原的世界，掉落在了蒙德城，然后系统给他派了一个前往风龙废墟的任务。 在蒙德，有 $n$ 个地点，编号为 $1, 2, 3, \ldots, n$。两个地点之间有 $m$ 条双向道路连接着两个地点，从某个地点到另一个地点，会遭到路上怪物的攻击，进而损失一定的血量。 每次经过一个地点，都会被原里面的 $NPC$ 收取一定数量的摩拉（包括起点和终点），而且路上并没有 $NPC$。 假设 $1$ 是蒙德城，$n$ 是风龙废墟，而小怂的血量总共为 $b$。他从蒙德城出发前往风龙废墟，出发时他的血量是满的。如果他的血量降低至负数，则无法到达风龙废墟。 小怂不想花太多摩拉，但他有点笨，所以他想知道，在可以到达风龙废墟的情况下，他所经过的所有地点中最多的一次收费的最小值是多少。 ### 输入格式 第一行 $3$ 个整数，$n, m, B$，分别表示 $n$ 个城市，$m$ 条公路，小怂的血量为 $B$。 接下来 $n$ 行，每行 $1$ 个正整数 $f_i$，表示经过城市 $i$ 需要交 $f_i$ 个摩拉。 再接下来 $m$ 行，每行 $3$ 个正整数，$a_i, b_i, c_i$ $(1 \leq a_i, b_i \leq n)$，表示地点 $a_i$ 和地点 $b_i$ 之间有一条道路，如果从此过，小怂会损失 $c_i$ 点血量。 数据保证： $1 \leq n \leq 10^4$，$1 \leq m \leq 5 \times 10^4$，$1 \leq B \leq 10^9$，$1 \leq c_i \leq 10^9$，$1 \leq f_i \leq 10^9$。 ### 输出格式 仅一个整数，表示小怂交摩拉最多的一次的最小值。 如果他无法到达风龙废墟，输出 $-1$。 ### 样例输入 ```plaintext 4 4 8 8 5 6 10 2 1 2 2 4 1 1 3 4 3 4 3 ``` ### 样例输出 ```plaintext 10 ``` ### 样例解释 小怂起点在地点 $1$，缴费 $8$ 个摩拉。 从地点 $1$ 走到地点 $2$，损失 $2$ 点血量，缴费 $5$ 个摩拉。 从地点 $2$ 走到地点 $4$，损失 $1$ 点血量，缴费 $10$ 个摩拉。 因此，小怂有 $8$ 点血量，共损失 $3$ 点血量，最多一次缴费的最小值是 $10$ 个摩拉。