1695: 捉拿逃犯

       一名在逃罪犯潜入了x城市，警察己掌握了他现在的居住地点 y， 以及接下来他要继续去报复若干名报案人的行动方案。警察从公安局(1号结点)急速出发前去捉拿逃犯。

      现给定 x城市的 n个关键位置点及m条道路组成的无向图及逃犯的行动变化路线，请你计算出警察最快需要多少时间抓住罪犯。

       注意逃犯开始的起点是 y，最后会停留在最后一个点不动。而且，逃犯变化总是在前（即如果它变化的同时警察到达了，则他先离开）。但是警察可以在罪犯行动到报复地点前等着抓罪犯。(见下图，输入输出数据见说明。)

输入第一行三个整数，分别为 n个位置点、m条道路及罪犯的居住地点 y。

接下来m行，每行三个整数a,b,c; 表示a到b之间有一条双向边，c表示通过这条边需要 c时间。

第m+1行一个整数 T，表示罪犯的行动位置变化的次数。

接下来 T行，每行两个数 ti 和 k, 表示罪犯将在第 ti个单位时间内流窜到 k 结点上去。 

5 7 3
1 2 3
1 4 7
2 3 5
2 5 6
3 4 6
3 5 2
4 5 4
3
18 2
3 5
8 4

8