11240.宝藏（treasure）

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

• 他发现这座山一共有 ( N ) 个山洞和 ( M ) 个暗道。每一个山洞里都有宝藏，第 ( i ) 个山洞里有无限份价值为 ( A_i ) 的宝藏，壮壮经过山洞 ( 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 )，表示山洞 ( i ) 中的宝藏价值。
• 接下来 ( M ) 行，每行三个整数 ( X_i )、( Y_i ) 和 ( Z_i )，表示暗道 ( i ) 从山洞 ( X_i ) 单向通向 ( Y_i )，且耗费体力值 ( Z_i )。

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

• 10% 的数据：题目馈赠。
• 30% 的数据：1 ≤ ( N ) ≤ 10，1 ≤ ( M ) ≤ 20。
• 50% 的数据：1 ≤ ( N ) ≤ 20，1 ≤ ( M ) ≤ 50。
• 70% 的数据：1 ≤ ( N ) ≤ 150，1 ≤ ( M ) ≤ 500。
• 100% 的数据：
  • ( 1 \le Z_i, T \le 500 )
  • ( 1 \le N, X_i, Y_i \le 1000 )
  • ( 1 \le M \le 10000 )
  • ( 0 \le A_i \le 10000 )