猫和老鼠所在的庄园可以视为一张由 n 个点和 m 条带权无向边构成的连通图。结点依次以 1,2,\ldots,n 编号，结点 i （ 1 \leq i \leq n ）有价值为 c_i 的奶酪。在 m 条带权无向边中，第 i （ 1 \leq i \leq m ）条无向边连接结点 u_i 与结点 v_i ，边权 w_i 表示猫和老鼠通过这条边所需的时间。

猫窝位于结点 a ，老鼠洞位于结点 b 。对于老鼠而言，结点 u 是安全的当且仅当：

• 老鼠能规划一条从结点 u 出发逃往老鼠洞的路径，使得对于路径上任意结点 x （包括结点 u 与老鼠洞）都有：猫从猫窝出发到结点 x 的最短时间 严格大于 老鼠从结点 u 沿这条路经前往结点 x 所需的时间。

老鼠在拿取安全结点的奶酪时不存在被猫抓住的可能，但在拿取不是安全结点的奶酪时则不一定。为了确保万无一失，老鼠决定只拿取安全结点放置的奶酪。请你计算老鼠所能拿到的奶酪价值之和。

第一行：两个正整数 n, m ，分别表示图的结点数与边数。

第二行：两个正整数 a, b ，分别表示猫窝的结点编号，以及老鼠洞的结点编号。

第三行： n 个正整数 c_1, c_2, \ldots, c_n ，表示各个结点的奶酪价值。

接下来 m 行中的第 i 行（ 1 \leq i \leq m ）包含三个正整数 u_i, v_i, w_i ，表示图中连接结点 u_i 与结点 v_i 的边，边权为 w_i 。

输出一行，一个整数，表示老鼠所能拿到的奶酪价值之和。

数据范围

• 对于 40\% 的测试点，保证 1 \leq n \leq 500 ， 1 \leq m \leq 500 。

• 对于所有测试点，保证 1 \leq n \leq 10^5 ， 1 \leq m \leq 10^5 ， 1 \leq a, b \leq n 且 a \neq b ， 1 \leq u_i, v_i \leq n ， 1 \leq w_i \leq 10^9 。

GESP25年12月八级

GESP八级25年12月图论优先队列BFS