上学

题目描述

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

输入格式

第⼀⾏，四个正整数 ，分别表⽰ C 城的结点数与边数，学校所在的结点编号，以及⼩ A 同学们的数量。 接下来 ⾏，每⾏三个正整数 ，表⽰ C 城中的⼀条⽆向边。 接下来 ⾏，每⾏⼀个正整数 ，表⽰⼀位同学的情况。

输出格式

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

样例输入 #1

5 5 3 3
1 2 3
2 3 2
3 4 1
4 5 3
1 4 2
5
1
4

样例输出 #1

4
3
1

数据范围

对于 % 的测试点，保证 。 对于另外 % 的测试点，保证 ， 。 对于所有测试点，保证 ， ， ， ， 。 保证给定的图联通。

知识点与难度

本题涉及的知识点从属于 GESP 8级，难度等级：⭐⭐⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。