U534156 赛艇表演（show）（T3）

$\qquad\!\!$LHRG李 想要去观看赛艇表演。由于路途遥远，他找到了具有拓荒能力的 npy VanHelsing 一起上路。

$\qquad\!\!$赛艇表演举行在一个具有 $n$ 个城市的国家中，这 $n$ 座城市通过 $m$ 条双向道路相互连接，通过每条道路都需要花费 $w$ 天。 $\qquad\!\!$想要举办赛艇表演，就需要这个城市在水路上。LHRG李 发现，这个国家中在水路上的城市都被称之为**枢纽**，**即存在两个与这个城市相连的城市只有通过该城市才能互相到达**。 $\qquad\!\!$LHRG李 首先需要知道去哪些城市能够观看表演，在此之后，他就要从他到达这个国家的第一个城市 $s$ 出发，前往任意一个枢纽去观看表演。不过对于每个枢纽，都需要他先在这个城市中暂住 $c$ 天，才能拿到入场券观看表演。 $\qquad\!\!$为了减少长途跋涉的时间，VanHelsing 可以随时拓荒出一条从一个**非起点并且非枢纽**的城市到另一个**非起点并且非枢纽**的城市的单向道路，不过通过这条单向道路需要花费 $val$ 天。 $\qquad\!\!$所以请问，LHRG李 从 $s$ 点出发到观看到赛艇表演所需的最短时间是多少？

第一行四个正整数 $n$，$m$，$s$ 和 $val$，表示城市个数、双向道路数，起点编号以及通过拓荒出的道路的花费。 第二行到第 $m+1$ 行，每行三个正整数 $u$，$v$ 和 $w$，表示每条双向道路的两端以及通过它花费的天数。 第 $m+2$ 到第 $m+n+1$ 行，每行一个正整数 $c$，表示如果这个点是枢纽，则需要在这个点暂住 $c$ 天才能获得入场券。

第一行输出由小到大输出所有枢纽的编号，中间以空格分隔。 第二行输出一个正整数，表示LHRG李 从 $s$ 点出发到观看到赛艇表演所需的最短时间。 **数据保证 LHRG李 一定能够看到赛艇表演。**

数据范围： | 子任务 | 测试点编号 | 总分数 | 数据范围 | 特殊性质 | | :----: | :----: | :----: | :----: | :----: | | **Subtask #1** | $1-4$ | 8 | $1\leqslant n \leqslant 10\\1 \leqslant m \leqslant 20$ | | **Subtask #2** | $5-8$ | 8 | $1\leqslant n \leqslant 100\\1\leqslant m \leqslant 1000$ | | **Subtask #3** | $9-12$ | 8 | $1\leqslant n \leqslant 5000\\1\leqslant m \leqslant 10^6$ | | **Subtask #4** | $13-16$ | 12 | $1\leqslant n \leqslant 10^5\\1 \leqslant m \leqslant 2\times 10^6$ | A | | **Subtask #5** | $17-20$ | 12 | $1\leqslant n \leqslant 10^5\\1 \leqslant m \leqslant 2\times 10^6$ | B | | **Subtask #6** | $21-24$ | 12 | $1\leqslant n \leqslant 10^5\\1 \leqslant m \leqslant 2\times 10^6$ | C | | **Subtask #7** | $25-34$ | 40 | $1\leqslant n \leqslant 2\times10^5\\1 \leqslant m \leqslant 2\times 10^6$ | 特殊性质 $A$：只存在一个枢纽。 特殊性质 $B$：所有 $w,val,c$ 值相同。 特殊性质 $C$：$val \geqslant \sum w +\sum c$。 对于$100\%$的数据，$1\leqslant n \leqslant 10^5$,$1\leqslant m \leqslant 2\times 10^6$,$1\leqslant w,c \leqslant 10^6$,$1\leqslant val \leqslant 10^7$ [题解](http://lhrg.github.io/题解-U534156-【赛艇表演】/) ------------ 出题者：LHRG李