You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

T4 喵喵（meow）

题目描述

小 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 输入

5 6 2
1 2 3 4 5
1 2 5
1 3 3
2 4 3
3 4 5
4 5 2
3 5 7

样例 1 输出

40

样例 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$。