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 * 10^5 ，1<=m<=2 * 10^5 ，1<=q<=2 * 10^5，1<=ui,vi,s,hi<=n ，1<=li<=10^6 。保证给定的图联通。