P3264 [JLOI2015] Pipeline Connection

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.

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 a single integer on one line, the minimum total amount of resources required so that any two stations with the same channel are connected.

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