A5186. [GESP202503 八级] 上学

C 城可以视为由 n 个结点与 m 条边组成的无向图｡这些结点依次以 $1,2, ..., n$ 标号,边依次以 $1,2, ..., m$ 标号｡第 条边( $(1 ≤i ≤m)$ )连接编号为 $u_{i}$ 与 $v_{i}$ 的结点,长度为 $l_{i}$ 米。
小 A 的学校坐落在 C 城中编号为 的结点｡小 A 的同学们共有 q 位,他们想在保证不迟到的前提下,每天尽可能晚 地出门上学｡但同学们并不会计算从家需要多久才能到学校,于是找到了聪明的小 A｡第 i 位同学( $(1 ≤i ≤q)$ )告 诉小 A,他的家位于编号为 $h_{i}$ 的结点,并且他每秒能行走 1 米｡请你帮小 A 计算,每位同学从家出发需要多少秒才 能到达学校呢?
接下来 q 行,每行一个正整数 $h_{i}$ ,表示一位同学的情况｡

第一行,四个正整数 n , m ,s, q ,分别表示 C 城的结点数与边数,学校所在的结点编号,以及小 A 同学们的数量｡
接下来 m 行,每行三个正整数 $u_{i}$ , $v_{i}$, $l_{i}$ ,表示 c 城中的一条无向边｡

对于 20% 的测试点,保证 q=1 。
对于另外 20% 的测试点,保证 1 ≤n ≤500, 1 ≤m ≤500
对于所有测试点,保证 $1 ≤n ≤2 ×10^{5}$ , $1 ≤m ≤2 ×10^{5}$ , $1 ≤q ≤2 ×10^{5}$ ,1≤ $u_{i}$ , $v_{i}$, $l_{i}$ , $s_i$ ≤n, $1 \le l_i \le 10^6$。 保证给定的图联通｡