U604043 伤感的jy

jy，今伤感之。zxy的离开似乎抽走的他生活中最大的乐观，使他整个人陷入一种低迷之中... 他回忆起与zxy走过校园的一条条小径，在某个角落悄悄低语，是如此令人怀念。

校园里有$N$个角落，对于jy来说，每个角落里都藏着曾经的美好回忆，我们定义它的值为$a_i$。其中的$M$条小路，从独特的一段走向另一端，同样带来不可割舍的回忆值$b_i$（也就是说，他们是单向的）。 假设你是DW，你希望带着jy回忆起更多的美好时光。你们从1号节点出发，为了提高效率，你们最多只会走$K$条没有甜蜜回忆的单向道路（在校园里，每两个地方之间都有一条路，对吧）。试求jy走过的路程中的最大回忆值$S$。

第一行，三个数，$N,M,K$ 接下来$N$个数，每个地方的回忆值$a_i$ 接下来$M$行，每行3个数，代表每条路的起点、终点及回忆值$b_i$

一个数，即答案$S$

$N \le 10^3, M \le 3 \times 10^5$ 每个地方、小径的回忆值只算一次