### 问题描述 小齐有一片农场，有 $N$ 个田地，编号为 $1$ 到 $N$，并且有一个位于田地 $1$ 的牛棚。每天晚上，小齐在牛棚敲响巨大的钟声，召唤他的奶牛回到牛棚吃晚餐。奶牛们会选择从它们所在的田地走一条最短的路径回到牛棚。 每个田地 $i$ 都有 $c_i$ 头奶牛。奶牛们听到钟声后，会沿着一条耗时最短的路径走到牛棚。如果有多条路径的耗时相同，奶牛们会选择“字典序”最小的路径。即，在路径的第一个不同的地方，奶牛们会选择走到较小编号的田地。 小齐发现有些田地离牛棚比较远，为了优化奶牛们的行走路径，他准备添加一条额外的“捷径”小路，这条小路的耗时为 $T$。这条小路直接连接牛棚（田地 $1$）和其他某个田地。奶牛在行走时，如果发现捷径小路可以更快地到达牛棚，它们就会选择经过捷径小路。 请帮助小齐确定通过添加捷径小路，能够使奶牛们的总行走时间减少的最大值。 ### 输入格式 第一行包含三个整数 $N$、$M$ 和 $T$，表示田地数量、已有路径数量，以及捷径小路的耗时。 第二行包含 $N$ 个整数 $c_1, c_2, \ldots, c_N$，表示每个田地的奶牛数量 $(0 \leq c_i \leq 10,000)$。 接下来 $M$ 行，每行包含三个整数 $a, b, t$，表示一条已有路径连接田地 $a$ 和田地 $b$，该路径的耗时为 $t$ $(1 \leq t \leq 25,000)$。 ### 输出格式 输出一个整数，表示通过添加捷径小路，奶牛们的总行走时间减少的最大值。 ### 样例输入 ``` 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 \leq N \leq 10,000，N-1 \leq M \leq 50,000，1 \leq T \leq 10,000$。