Background

Beginner lty made a problem, but he was too weak, so he wanted czx, who likes “letting pigeons” (fang ge zi), to help him write a std. However, czx went to “let pigeons” again, so he did not write the std. Beginner lty felt looked down upon by his senior, so he decided to go to the place where czx is “letting pigeons” to find him.

Problem Description

The place where czx is “letting pigeons” is a park. The park can be seen as an undirected graph with $n$ nodes and $m$ edges (self-loops are guaranteed not to exist). lty will enter from the entrance of the park (node $b$) to look for czx. czx’s initial position is $e$. Then, at time $a_i$, czx will change his position to node $x$. Before that, lty already knows czx’s exact position and his future movement plan. Now beginner lty wants to know the minimum time needed to catch czx.

UPD:

The graph is guaranteed to be connected, and czx will finally stay at one place and stop moving.

Input Format

The first line contains four integers $n, m, b, e$. The meanings of $b$ and $e$ are as described in the statement.

The next $m$ lines each contain three integers $x, y, z$, indicating there is a bidirectional edge between $x$ and $y$, and it takes lty $z$ time to traverse this edge.

The $(m+1)$-th line contains an integer $T$, indicating the number of times czx changes his position.

The next $T$ lines each contain two integers $a_i$ and $x$, indicating that at time $a_i$, czx will move to node $x$.

Output Format

Output one integer, the minimum required time.

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

Sample explanation:

At the beginning, go directly to node $2$, then wait for czx to come. The total time cost is $9$ units of time.

For 30% of the testdata, $n \le 100, m \le 1000, T \le 100$.

For another 30% of the testdata, $T = 0$.

For 100% of the testdata, $n \le 10^5, m \le 5\times10^5, T \le 10^5$.

The testdata guarantees that all times fit in the range of int.

Note: At any time when czx starts moving, czx teleports first, and then lty moves. That is, lty cannot catch czx at the node before he teleports at the teleport moment, but lty can wait at the destination node and catch him there.

Translated by ChatGPT 5