小 E 大抵是一位爱猫人士。

小 E 每天晚上都会摇响铃铛，召集喵喵街 96 号的流浪猫们，向它们投喂食物。可怜的流浪猫们为了尽快获得食物，都会选择最短时间的可能路线前往小 E 所在的位置。

为了方便描述，喵喵街 96 号分为 n 个地点，编号为 1 至 n，小 E 的食物投喂点处在点 1。不同点之间通过 m 条双向小径连接。每条小径都有一个与之相关的通行时间，并且每个点都能通过一些小径与点 1 联通。

点 i 处有 c_i 只流浪猫，在小 E 摇响铃铛后，这些流浪猫会沿着花费时间最少的路径前往点 1，当某两条路径花费时间相同时，它们会选择编号字典序较小的一条（这里的编号是指点的编号，如路径 7 \rightarrow 3 \rightarrow 6 \rightarrow 1 与 7 \rightarrow 5 \rightarrow 1 两条路径在花费时间相同的前提下，会选择前者）。容易发现，对于同处点 i 的流浪猫，它们选择的路径相同且唯一。

我们将每只猫到达点 1 所用的最短时间之和成为总时间。为了让流浪猫尽可能少赶路，小 E 希望通过增加一条通行时间为 t 的捷径（同样为双向路径），连接点 1 与一个其它点，来减少总时间。但是由于流浪猫们已经熟悉了原来的路线，当它们在通往 1 号点的常规路径中偶然发现这条捷径，如果它能帮助它们更快地到达1 号点，它们就会选择这条捷径。否则，即使可能使用捷径来改善通行时间，它们也会按照原来的路线行走。

现在，小 E 希望你能帮助他求出增加这条路后能减少总时间的最大值。

第一行输入三个数字 n,m,t，分别表示点数，边数，以及增加的路径的通行时间。

第二行输入 n 个整数 c_i，表示点 i 出的流浪猫数量。

接下来 m 行，每行包括三个整数 a,b,d，表示一条连接点 a 与点 b 的双向路径，通行时间为 d。

共一行，输出一个整数，表示增加一条路后能减少总时间的最大值。

样例 1 解释

最优方案为再 1,5 之间增加一条通行时间为 2 的捷径。

数据规模与约定

- 对于 30\% 的数据，保证 n \le 5。

- 对于 50\% 的数据，保证 n \le 500。

- 对于另 20\% 的数据，保证 m = n - 1。

- 对于另 20\% 的数据，保证 t = 1 \times 10^9。

- 对于 100\% 的数据，保证 1 \le n \le 1 \times 10^4, n - 1 \le m \le 5 \times 10^4,1 \le t \le 1 \times 10^9,0\le c_i\le 1 \times 10^4,1\le d \le 2.5 \times 10^4。