上学

题目描述

C 城可以视为由 $n$ 个结点与 $m$ 条边组成的无向图。

这些结点依次以 $1, 2, \ldots, n$ 标号，边依次以 $1 \le i \le m$ 编号。第 $i$ 条边连接编号为 $u_i$ 与 $v_i$ 的结点，长度为 $l_i$ 米。

小 A 的学校坐落在 C 城中编号为 $s$ 的结点。小 A 的同学们共有 $q$ 位，他们想在保证不迟到的前提下，每天尽可能晚地出门上学。但同学们并不会计算从家需要多久才能到学校，于是找到了聪明的小 A。

第 $i$ 位同学（$1 \le i \le 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 \le n \le 500$，$1 \le m \le 500$；
• 对于所有测试点，保证 $1 \le n \le 2 \times 10^5$，$1 \le m \le 2 \times 10^5$，$1 \le q \le 2 \times 10^5$，$1 \le u_i, v_i, s, h_i \le n$，$1 \le l_i \le 10^6$，且保证给定的图连通。