Description

Xiao Mingming recently joined an intelligence department, which is struggling with how to establish secure pipeline connections. The department has $n$ intelligence stations, numbered from $1$ to $n$. You are given $m$ pairs of stations $(u_i,v_i)$ with a cost $w_i$, meaning that a pipeline can be built between station $u_i$ and station $v_i$ at a resource cost of $w_i$.

If one station can reach another station through several built pipelines, then these two stations are considered connected. Formally, if a pipeline is built between $u_i$ and $v_i$, then they are connected; if $u_i$ and $v_i$ are both connected to $t_i$, then $u_i$ and $v_i$ are also connected.

Among all stations, there are $p$ important stations, and each of these stations has a specific channel. The task is to spend the minimum total amount of resources so that any two stations with the same channel are connected.

Input Format

The first line contains three integers $n,m,p$, representing the number of stations, the number of possible pipelines, and the number of important stations.

Each of the next $m$ lines contains three integers $u_i,v_i,w_i$, describing a possible pipeline.

Finally, there are $p$ lines, each containing two integers $c_i,d_i$, representing the channel and the station index of an important station.

Output Format

Output a single integer on one line, the minimum total amount of resources required so that any two stations with the same channel are connected.

5 8 4
1 2 3
1 3 2
1 5 1
2 4 2
2 5 1
3 4 3
3 5 1
4 5 1
1 1
1 2
2 3
2 4

4

Hint

Choose $(1,5)$, $(3,5)$, $(2,5)$, $(4,5)$ to connect these $4$ pairs of stations.

For $100\%$ of the testdata, $1\le c_i\le p\le10$, $1\le u_i,v_i,d_i \le n \le 1000$, $0\le m \le 3000$, $0\le w_i \le 2\times 10^4$.

Translated by ChatGPT 5