该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述（miao）

强哥是一位热心的社区志愿者，他负责照顾社区里的流浪猫。

强哥每天晚上都会在社区中心（地点1）摇响铃铛，召集各处的流浪猫来享用晚餐。为了尽快吃到食物，猫咪们都会选择耗时最短的路线前往社区中心。

社区有 $n$ 个地点，编号为 $1$ 至 $n$，社区中心在点 $1$。不同地点之间通过 $m$ 条双向小路连接，每条小路都有一个通行时间。每个地点都能通过一些小路径到达点 $1$。

地点 $i$ 处有 $c_i$ 只流浪猫。当强哥摇响铃铛后，这些猫咪会沿着耗时最少的路径前往点 $1$。如果存在多条耗时相同的路径，它们会选择经过地点的编号字典序较小的那条（例如路径 $7 \rightarrow 3 \rightarrow 6 \rightarrow 1$ 与 $7 \rightarrow 5 \rightarrow 1$ 在耗时相同时，会选择前者）。对于同一地点的猫咪，它们选择的路径是唯一确定的。

所有猫咪到达点 $1$ 所用的最短时间之和称为总时间。为了减少猫咪们的奔波，强哥计划修建一条新的捷径（双向路径），连接点 $1$ 与另一个地点，通行时间为 $t$。不过，猫咪们只会在这条捷径确实能帮它们更快到达目的地时才会使用它，否则它们仍按原路线行走。

现在，强哥希望你能帮助他计算，修建这条捷径后，最多能减少多少总时间。

输入格式 (miao.in)

第一行输入三个整数 $n,m,t$，分别表示地点数量、小路数量、以及新建捷径的通行时间。

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

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

输出格式 (miao)

输出一行一个整数，表示修建捷径后能减少的总时间的最大值。

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

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