测试数据来自 system/1333

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

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　每天早上，妙高镇的娃娃们都会前往中心校上学。学生们都会沿着最短的路径行走。

　　妙高镇共有 \(n\) 个自然村，方便起见编号为 \(1..n\)，镇中心校位于1号村庄。村庄之间由 \(m\) 条双向的小路连接。每条小路有其通过时间，从每个村庄出发都存在一条由一些小路组成的路径可以到达中心校。

　　经统计，村庄 \(i\) 中有 \(c_i\) 名中心校的学生。每天早上，这些学生都沿着一条消耗最少时间的路径步行前往中心校。如果有多条路径并列消耗时间最少，学生们会选择其中“字典序”最小的路径，也就是说，她们通过在两条路径第一次出现分支的位置优先选择经过编号较小的村庄的方式来打破并列关系，所以经过村庄7,3,6,1的路径会优先于经过7,5,1的路径，如果它们所消耗的时间相同。

　　镇长担心中心校距离某些村庄太远。他计算了每位学生路上的时间，将所有学生消耗的时间相加，称这个和为总耗时。他想要新修建一条连接中心校（1号村庄）和另一个村庄的通过时间为 \(T\) 的道路来尽可能地减少总耗时。当一名学生在她平时前往中心校的路上偶然看见这条新道路时，如果这条新道路能够使她更快地到达中心校，她就会走这条路。否则，即使这条新道路可能会减少到达中心校的行走时间，但他按平常习惯的路径上不会遇到这条新道路，他仍然会沿着习惯的道路行走。

　　请帮助镇长求出通过新建一条道路能够达到的总耗时减少量的最大值。

【输入格式】

　　输入的第一行包含 \(n,m\) 和 \(T\)，意义如题目描述。
　　以下 \(n\) 行包含 \(c_1…c_n\)，均为大于等于 0 且小于等于 10000 范围内的整数。
　　以下 \(m\) 行，每行由三个整数 \(a,b\) 和 \(t\) 描述了一条小路，这条小路连接了村庄 \(a\) 和 \(b\)，通过时间为 \(t\)。所有的通过时间在大于等于 1 且小于等于 25000。

【输出格式】

　　输出镇长可以达到的总耗时的最大减少量。

【输入输出样例】

　Input

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

　Output

40

【样例解释】

　　样例图示如下，蓝色数字代表该村庄的学生人数：

　　每个点到中心校 1 号村庄的路径为：
　　◆2 到 1：2->1，长度为 5，耗时：2*5=10；
　　◆3 到 1：3->1，长度为 3，耗时：3*3=9；
　　◆4 到 1：4->2->1，长度为 8，耗时：4*8=32；
　　◆5 到 1：5->3->1，长度为 10，耗时：5*10=50；
　　在 1 到 5 之间新建一条用时为 2 的道路，则 5 号村庄的学生到中心校直接走新建道路，耗时为：5*2=10，所以总耗时减少量为：50-10=40。

【数据限制】

　　\(100\%\) 的数据满足：\(1≤n≤10,000\)，\(n−1≤m≤50000\)，\(1≤T≤10000\)。

【来源】

　　Mr.he