跨宇宙跳跃

时间限制： 每个测试点 2 秒
内存限制： 256 MB
输入： 标准输入
输出： 标准输出

在《蜘蛛宇宙》中，宇宙之间旅行需要使用特殊的传送门。一个由 $m$ 个传送门连接 $n$ 个宇宙的网络是一个由 $n$ 个顶点和 $m$ 条边构成的图。每个传送门连接两个宇宙，且任意两个传送门不会连接同一对宇宙。

米格尔·奥哈拉使用他的高科技传送门手表进行移动。不过，早期版本的手表并没有那么先进，无法直接旅行到任意宇宙。具体来说，手表有一个能量等级参数，初始值为 $0$。

每个传送门有一个属性 $w$ ——使用该传送门所需的最小能量等级。如果手表的当前能量等级小于 $w$，则暂时无法使用该传送门。幸运的是，有一种方法可以提高能量等级：第一次进入宇宙 $i$ 时，手表的能量等级会永久增加 $a_i$。

米格尔想知道，如果他从宇宙 $s$ 出发，并访问所有他能到达的宇宙，那么他最终能获得的最大能量等级是多少？请帮他回答这个问题。

输入数据

第一行包含三个整数 $n, m, s$ ——宇宙的数量、传送门的数量以及米格尔出发的宇宙编号（$1 \le s \le n \le 10^5$，$1 \le m \le 2 \cdot 10^5$）。

第二行包含 $n$ 个整数 $a_i$ ——首次访问每个宇宙时能量等级的增加量（$1 \le a_i \le 10^9$）。

接下来 $m$ 行描述传送门。第 $i$ 个传送门的描述包含三个整数 $u_i, v_i, w_i$，表示连接宇宙 $u_i$ 和 $v_i$ 的传送门，使用它需要手表的能量等级不低于 $w_i$（$1 \le u_i, v_i \le n$，$0 \le w_i \le 10^9$）。

宇宙之间的连接图不包含重边和自环，但不一定连通。

输出一行一个整数 —— 米格尔能够获得的最大能量等级。

输入

输出

输入

输出