宝藏(treasure)

【题目描述】

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

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

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

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

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

【输入格式】

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

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

【输出格式】

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

【输入样例1】

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

【输出样例1】

14

配套文件参看treasure1.ans

【数据规模】

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

对于30%的数据，$1≤N≤10，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≤100000≤A_i≤10000$