题目描述

壮壮是一个爱探险的孩子。一天，他爬上了一座山，然后利用先进的遥感技术了解到了整座山的地形和内部构造。

他发现这座山一共有 $N$ 个山洞和 $M$ 个暗道。每一个山洞里都有宝藏，第 $i$ 个山洞里有无限份价值为 $A_i$ 的宝藏，壮壮经过山洞 $i$，就会领取山洞 中的一份宝藏(每次经过都能领取一份)。

每一个暗道都连通两个山洞，第 $i$ 个暗道连通了山洞 $X_i$ 和 $Y_i$，壮壮可以穿过暗道 $i$ 从山洞 $X_i$ 到达 $Y_i$，但是不可以穿过暗道 $i$ 从山洞 $Y_i$ 到达 $X_i$，但无论怎么穿过暗道 $i$，都要耗费一定的体力值 $Z_i$。

得知这些探洞信息后，壮壮马上开始准备去寻宝藏。已知壮壮的体力值上限为 $T$，他最多只能耗费 $T$ 的体力值。壮壮可以从任意一个山洞开始他的探索，但是只能穿过暗道去到别的山洞。

他每到达一个山洞，就会领取山洞中的一份宝藏。他想知道，他最多可以获得的宝藏价值之和为多少?

输入格式

第一行三个整数 $N,M$ 和 $T$，分别对应山洞的数量，暗道的数量，体力值上限；

第二行 $N$ 个整数，第 $i$ 个数是 $A_i$，表示山洞中的宝藏价值。

接下来 $M$ 行，每行都有三个数 $X_i$，$Y_i$ 和 $Z_i$，分别表示山洞 $i$ 连接的两个山洞的编号和穿过这个暗道所要耗费的体力值。

输出格式

输出一个整数，表示耗费的体力值不超过 $T$ 时，壮壮最多能获得的宝藏价值之和。

5 6 10
5 5 6 3 2
2 5 1
1 3 6
3 4 2
4 5 3
4 5 10
3 5 10

14

样例解释

样例中每一个点、边的情况如图所示，最优的走法是 $1$->$3$->$4$。

数据范围

$10\%$ 的数据是题目的馈赠。

对于 $30\%$ 的数据，$1≤N≤8$，$1≤M≤20$；

对于 $50\%$ 的数据，$1≤N≤20$，$1≤M≤50$；

对于 $70\%$ 的数据，$1≤N≤150$，$1≤M≤500$；

对于 $100\%$ 的数据，$1≤Z_i≤T≤500$，$1≤N, X_i,Y_i ≤1000$，$1≤M≤10000$，$0≤ A_i ≤10000$。