题目背景

蒟蒻 lty 出了一道题，但是由于太弱了，所以希望喜欢鸽子的 czx 来帮他写一个 std 。由于 czx 又放鸽子去了，所以没有写 std。蒟蒻 lty 觉得受到了学长的鄙视，所以决定去 czx 放鸽子的地方找他。

题目描述

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

UPD:

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

输入格式

第一行四个整数$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$ 个点上去。

输出格式

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

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

提示

样例解释：

在开始的时候就直接走到 $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 可以在他瞬移到的点等着抓他。