252.上学

C 城可以视为由 n 个结点与 m 条边组成的⽆向图 。这些结点依次以 1 , 2, , n 标号 ，边依次以 1 , 2, , m 标号 。第 i 条边（ 1 ≤ i ≤ m）连接编号为 ui 与 vi 的结点 ，长度为 li ⽶ 。 ⼩ A 的学校坐落在 C 城中编号为 S 的结点 。⼩ A 的同学们共有 Q 位 ，他们想在保证不迟到的前提下 ，每天尽可能晚 地出门上学 。但同学们并不会计算从家需要多久才能到学校 ，于是找到了聪明的⼩ A 。第 i 位同学（ 1 ≤ i ≤ Q）告 诉⼩ A ，他的家位于编号为 hi 的结点 ，并且他每秒能⾏⾛ 1 ⽶ 。请你帮⼩ A 计算 ，每位同学从家出发需要多少秒才 能到达学校呢？

第一⾏， 四个正整数 n, m, S, q ，分别表⽰ C 城的结点数与边数 ，学校所在的结点编号， 以及⼩ A 同学们的数量。 接下来 m ⾏ ，每⾏三个正整数 ui, vi , li ，表⽰ C 城中的一条⽆向边。 接下来 Q ⾏ ，每⾏一个正整数 hi ，表⽰一位同学的情况。

共 Q ⾏ ，对于每位同学 ，输出一个整数 ，表⽰从家出发到学校的最短时间。

对于 20% 的测试点 ，保证 Q = 1 。 对于另外 20% 的测试点 ，保证 1 ≤ n ≤ 500 ，1 ≤ m ≤ 500 。 对于所有测试点 ，保证 1 ≤ n ≤ 2 x 10^5 ，1 ≤ m ≤ 2 x 10^5 ，1 ≤ Q ≤ 2 x 10^5 ，1 ≤ ui , vi , 8, hi ≤ n，1 ≤ li ≤ 10^6 。 保证给定的图联通。