Secure Channel Connection

In a secret intelligence department, there are $n$ intelligence stations numbered from $1$ to $n$. There are $m$ undirected edges; the $i$-th edge connects station $u_i$ with station $v_i$ and costs $w_i$ units to build a secure channel. Two stations are said to be connected if there is a path (via built channels) between them.

Among these stations, there are $p$ important stations. Each important station is assigned a specific channel (an integer value). The task is to spend the minimal amount of resources (sum of edge costs) to build a subset of channels such that, for every channel, all important stations with that channel are connected (i.e. there is a path between any two important stations sharing the same channel).

Formally, suppose for each channel $c$, let $S_c$ be the set of important stations with channel $c$. You need to select some of the given edges such that for every channel $c$ with $|S_c| \ge 2$, the subgraph induced by the selected edges contains a path between any two stations in $S_c$. If it is impossible for some channel, output -1.

inputFormat

The input consists of several parts:

• The first line contains two integers $n$ and $m$, representing the number of stations and the number of available channels (edges).
• The following $m$ lines each contain three integers $u$, $v$, and $w$, indicating there is an undirected edge between station $u$ and station $v$ with cost $w$.
• The next line contains an integer $p$, the number of important stations.
• The following $p$ lines each contain two integers: a station id and its assigned channel.

Note: Station ids are in the range $1$ to $n$.

outputFormat

Output a single integer --- the minimum total cost required to build the channels so that, for every channel, all important stations sharing that channel are connected. If it is impossible to connect the important stations for some channel, output -1.

sample

4 4
1 2 1
2 3 2
3 4 3
1 4 10
2
2 1
4 1

5