题目描述

伞伞所在的国家有 $n$ 个城市，其中伞伞位于城市 $s$ 。城市之间共有 $m$ 条双向道路，第 $i$ 条道路连接城市 $u_i$ 和城市 $v_i$ ，通过这条道路需要花费 $t_i$ 的时间。

除此之外，每个城市都有一座传送门 $a_i$ ，通过传送门可以花费 $|a_i-a_j|$ 的时间从任意城市 $i$ 到达任意城市 $j$ 。

这个国家会不定时地在各个城市举行宴会，伞伞想知道，他从城市 $s$ 出发，前往城市 $i$ 参加宴会的最少花费时间是多少，你需要对 $i=1,2,3,...,n$ 求出答案。

输入格式

从文件 party.in 读入数据。第一行包含两个整数 $n,m,s$ ，表示城市数量、道路数量和伞伞所在的城市。

接下来一行 $n$ 个整数 $a_i$ ，表示城市 $i$ 的传送门参数。

接下来 $m$ 行，每行三个整数 $u_i,v_i,t_i$ 表示第 $i$ 条道路连接城市 $u_i$ 和城市 $v_i$ ，通过这条道路需要花费 $t_i$ 的时间。

输出到文件 party.out。一行 $n$ 个整数，第 $i$ 个表示从城市 $s$ 到城市 $i$ 的最少花费时间，相邻两个整数用一个空格隔开。

0 2 4

6 7 5
-5 3 100 3 20 0
1 2 7
2 3 4
3 4 50
4 5 1
5 6 9
1 6 30
2 5 12

8 1 5 1 0 4

对于第一组数据，城市 $1$ 到城市 $2$ 直接走道路花费 $2$ ，到城市 $3$ 走传送门花费 $|9-7|=2$ （也可以先到城市 $2$ 再走道路，花费 $2+3=5$ ），故取较小值。

下发文件分别对应子任务 $1,2,3,4,5$ 。

子任务编号	$n \leq$	$m \leq$	分值
$1$	$10$		$10$
$2$	$3 \times 10^2$	$2 \times 10^5$	$10$
$3$	$10^3$	$2 \times 10^5$	$20$
$4$	$5 \times 10^3$		$30$
$5$	$2 \times 10^5$		$30$

对于 $100\%$ 的数据：保证 $1 \le n,m\le 2 \times 10^5,1 \le s \le n,-10^9 \le a_i \leq 10^9,1 \le u_i , v_i \le n,u_i \neq v_i,1 \leq t_i \leq 10^9$。

时空限制： $1$ 秒 / $256\,\mathrm{MiB}$ 。