Description

czx 放鸽子的地方是一个公园，公园可以看作是由 $n$ 个点 $m$ 条边组成的无向图（保证无自环），lty 将从公园的入口（$b$ 号节点）进去寻找 czx，czx 刚开始的位置为 $e$，而 czx 会在 $a_i$ 个单位时间时变化位置到第 $x$ 个节点去，在此之前 lty 已经知道了 czx 的具体位置和接下来他位置的变化方案，蒟蒻 lty 现在想知道他至少需要花多少时间找到 czx。

UPD:

保证图连通，czx 最后会待在一个地方不动。

Input Format

第一行四个整数 $n,m,b,e$。$b$ 和 $e$ 的意义如题面所示。

接下来 $m$ 行，每行三个整数 $x,y,z$，表示 $x$ 到 $y$ 之间有一条双向边，lty 走这条边要花费 $z$ 的时间。

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

接下来 $T$ 行，每行两个整数 $a_i$ 和 $x$，表示 czx 将在第 $a_i$ 个单位时间时移动到第 $x$ 个点上去。

Output Format

一个整数，表示最短所需时间。

6 9 1 6
1 2 1
1 3 3
1 4 4
2 3 2
3 6 6
4 5 6
2 5 9
3 5 7
5 6 2
3
10 3
8 5
9 2

9

Hint

样例解释：

在开始的时候就直接走到 $2$ 号节点，然后等到 czx过来。总花费时间 $9$ 个单位时间。

对于 30% 的数据，$n\le 100,m\le 1000,T\le 100$

对于另外 30% 的数据，$T=0$

对于 100% 的数据，$n \le 10^5,m \le 5\times10^5,T \le 10^5$

数据保证所有时间在 int 范围内

注意：在任意一个 czx 开始移动的时间点，都是 czx 先瞬移，然后 lty 再行走，也就是说， lty 不能在 czx 瞬移的时候到他瞬移前的点抓住他，但是 lty 可以在他瞬移到的点等着抓他。