题目描述

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

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

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

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

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

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

输入格式

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

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

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

输出格式

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

样例

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

40