题目背景

小王最近痴迷于打游戏，但是他太菜了qwq，想让你帮他玩一玩嘿嘿嘿

题目描述

在未来世界，人类开发并移居到了 $n$ 颗星球上。这些星球之间由 $m$ 个单向的虫洞构成了一张不含重边和自环的有向无环图。小王从星球 $s$ 出发进行星际旅行，每次都会在一个虫洞中使用传送器进行穿梭，目的地是星球 $t$。由于穿梭于虫洞之中可能会遇到各种危险，因此当小图灵从星球 $i$ 传送到星球 $j$ 时需要保证传送器的能量大于等于 $w_{ij}$（此过程中不会消耗传送器的能量）。

同时，每经过一颗星球 $k$，小王就会在那颗星球上停留 $t_k$ 天进行游览（包含星球 $s$ 和星球 $t$）。然而小王的假期只有 $c$ 天，现在小王想请知道，最少向传送器中注入多少能量，能够保证小王能够在假期内成功游览目的地星球 $t$ 。

输入格式

第一行输入四个正整数 $n,m,s,t,c$，分别表示星球的数量，虫洞的数量，起点星球，终点星球和小王的假期时间。

接下来一行 $n$ 个正整数，第 $i$ 个正整数 $v_i$ 表示如果经过第 $i$ 颗星球，小王会停留的时间。

接下来 $m$ 行，每行三个正整数 $x,y,w_{xy}$，表示星球 $x$ 与星球 $y$ 之间存在一个虫洞，由 $x$ 穿梭到 $y$ 需要的传送器能量大于等于 $w_{xy}$ 。

输出格式

一个正整数，表示传送器最少要注入的能量是多少。

样例

6 6 1 2 6
1 1 1 1 1 1 
5 2 72
1 3 44
3 4 84
3 5 68
1 6 33
4 2 0

72

数据范围

对于 $20$% 的数据，$n,m\le 1000,w_{xy}\le 100,v_i=1$；

对于另外 $20$% 的数据，$n,m \le 100,w_{xy} \le 100$；

对于另外 $20$% 的数据，$v_i=1$；

对于 $100$% 的数据，$2 \le n \le 10^5, 1 \le m \le 2 \times 10^5, 1\le s,t,x,y \le n, 1\le c,v_i,w_{xy} \le 10^9$，保证存在至少一条路径使得小王能够成功完成游览。