C 城可以视为由 n 个结点与 m 条边组成的无向图。这些结点依次以 1, 2, \ldots, n 标号，边依次以 1, 2, \ldots, m 标号。第 i 条边（ 1 \leq i \leq m ）连接编号为 u_i 与 v_i 的结点，长度为 l_i 米。
小A的学校坐落在C城中编号为 s 的结点。小A的同学们共有 q 位，他们想在保证不迟到的前提下，每天尽可能晚地出门上学。但同学们并不会计算从家需要多久才能到学校，于是找到了聪明的小A。第 i 位同学（ 1 \leq i \leq q ）告诉小A，他的家位于编号为 h_i 的结点，并且他每秒能行走 1 米。请你帮小A计算，每位同学从家出发需要多少秒才能到达学校呢？
第一行，四个正整数 n, m, s, q ，分别表示 C 城的结点数与边数、学校所在的结点编号、以及小A同学们的数量。
接下来 m 行，每行三个正整数 u_i, v_i, l_i ，表示 C 城中的一条无向边。
接下来 q 行，每行一个正整数 h_i ，表示一位同学的情况。
共 q 行，对于每位同学，输出一个整数，表示从家出发到学校的最短时间。
5 5 3 3 1 2 3 2 3 2 3 4 1 4 5 3 1 4 2 5 1 4
4 3 1
对于20%的测试点，保证 q = 1 。
对于另外20%的测试点，保证 1 \leq n \leq 500 ， 1 \leq m \leq 500 。
对于所有测试点，保证 1 \leq n \leq 2 \times 10^5 ， 1 \leq m \leq 2 \times 10^5 ， 1 \leq q \leq 2 \times 10^5 ， 1 \leq u_i, v_i, s, h_i \leq n ， 1 \leq l_i \leq 10^6 。
保证给定的图联通。
2025年GESP 3月认证C++八级真题