Description

Once, in a kingdom, there were $m$ roads connecting $n$ cities, and between any two cities there was at most one direct road. After a severe war, $d$ roads were destroyed. The king wants to repair the country's road system. Now, traffic between two important cities $A$ and $B$ is interrupted, and the king hopes to restore the connection between these two cities as soon as possible. Your task is to repair some roads to restore the connection between $A$ and $B$, while minimizing the total length of the repaired roads.

Input Format

The first line contains an integer $n\ (2<n\le 100)$, representing the number of cities. These cities are numbered from $1$ to $n$.

The second line contains an integer $m\ (n-1\le m\le \dfrac{1}{2}n(n-1))$, representing the number of roads.

Each of the next $m$ lines contains $3$ integers $i,j,k\ (1 \le i,j \le n,i\neq j,0<k \le 100)$, indicating that there is a road of length $k$ directly connecting city $i$ and city $j$.

The next line contains an integer $d\ (1\le d\le m)$, representing the number of roads that were destroyed after the war. In each of the following $d$ lines, there are two integers $i$ and $j$, indicating that the road directly connecting city $i$ and city $j$ was destroyed.

The last line contains two integers $A$ and $B$, representing the two important cities whose traffic needs to be restored.

Output Format

Output a single integer, representing the minimal total length of roads that must be repaired to restore traffic between $A$ and $B$.

3
2
1 2 1
2 3 2
1
1 2
1 3

1

Hint

Translated by ChatGPT 5