上学

题目描述

C 城可视为由 n 个结点与 m 条边组成的无向图，结点以 1..n 标号。小 A 的学校在编号为 s 的结点。同学们共有 q 位，第 i 位同学的家在编号 p[i] 的结点，每秒能行走 1 米。请你计算每位同学从家出发需要多少秒才能到达学校。

输入格式

第一行四个正整数 n, m, s, q；接下来 m 行，每行三个正整数 u, v, l 表示一条无向边（长度 l 米）；接下来 q 行，每行一个正整数 p。

输出格式

共 q 行，每行一个整数，表示每位同学的最短时间。

样例

输入：5 5 3 3\n1 2 3\n2 3 2\n3 4 1\n4 5 3\n1 4 2\n5\n1\n4\n输出：\n4\n3\n1

数据范围

对于所有测试点，保证 1 ≤ n, m ≤ 2×10^5，1 ≤ s ≤ n，1 ≤ q ≤ 2×10^5，1 ≤ 边权 ≤ 10^9；保证给定图联通。