4326: T4 喵喵（meow）

## 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$。

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