U463989 小Y之捡树叶

小 Y 和这群人打了会儿篮球之后，意外的发现篮球场的旁边有一小树林，正好，其中有一人有收集树叶的癖好。于是小 Y 便跟随着大部队到树林里捡树叶，结果大家一致同意让小 Y 当苦力，于是小 Y 一气之下气了一下。

这个小树林里面一共有 $n$ 堆树叶,这 $n$ 堆树叶由 $m$ 条有向边连接，小 Y 一开始在编号为 $p$ 的树叶堆。每一堆树叶都有属于自己的重量，第 $i$ 堆树叶的重量为 $a_{i}$。 接下来小 Y 要把这 $n$ 堆树叶合并成一堆树叶给那个人。 我们定义和并若干个树叶堆的代价为：这若干个 **树叶堆的重量总和** 乘以所要经过这若干个树叶堆的 **路径长度之和**。（注：不一定经过一个树叶堆，就必须要合并这个树叶堆） 合并完若干个树叶堆之后，这若干个树叶堆可以看做一个点（可以理解成强连通的缩点），而这个点的重量就是这若干个树叶堆的重量之和。随后小 Y 就得从这个点出发，重新合并了。 不过众所周知，小 Y 是很懒的，所以请求出小 Y 最小花费的代价，不过有可能答案很大，所以说请对答案 $10^9 + 7$ 取模。

第一行为 $n,m,p$。 第二行，有 $n$ 个数代表每个树叶堆的重量。 接下来的 $m$ 行，每一行有三个数，分别代表一个有向边的起点、终点和长度。

一个整数代表最小花费的代价。

$1 \le p \le n \le 100$ $1 \le m \le 1000$ 重量和边权绝对值小于 $10^9$。