P9542 [Hubei NOI Qualifier Simulation 2023] Go Master / alphago

Xiao K is a Go player. After getting tired of traditional Go, he invented a new kind of Go. The new Go is a single-player game. The board of this game is an undirected connected graph with $n$ vertices and $m$ edges, with no multiple edges and no self-loops. Also, each edge has a weight, and the weight of the $i$-th edge is $w_i$. At the beginning of the game, each vertex may have one black stone, one white stone, or be empty. **At least one vertex is empty.** Next, the player needs to perform some operations. Each operation is as follows: First, choose a vertex $u$ that has no stone on it. It can be guaranteed that under the given constraints, such a vertex always exists. Next, for each stone, if it is on vertex $v$, the player must choose any **simple path** from $v$ to $u$, and move this stone one step along this simple path. Formally, a simple path is a vertex sequence $\{p_1,p_2 \ldots p_k\}$ that satisfies $p_1 = v$, $p_k = u$, $p_1,p_2 \ldots p_k$ are **all distinct**, and there is an edge between $p_i$ and $p_{i+1}$. After the operation, this stone will be moved to vertex $p_2$. Note that although at the start there is at most one stone on each vertex, after several operations there may be multiple stones on one vertex. For different stones on the same vertex, the chosen simple paths in one operation may be different. After performing any number of operations (possibly $0$), the player may **count territory**, i.e., settle the game score. For every pair of stones with different colors, if the vertices they are on are directly connected by an edge with weight $w$, then we say they **enclose this edge**, which gives the player $w$ **points**. The player's total **points** is the sum of the **points** produced by all such pairs of stones. Now Xiao K gives you the initial board configuration. Please help him find the maximum possible **points** that can be obtained on this board.

The input has $m + k + 1$ lines. The first line contains three integers $n,m,k$, denoting the number of vertices, edges, and stones. The next $k$ lines each contain two integers $x,c$, meaning there is a stone of color $c$ on vertex $x$. Here $c=0$ means a black stone, and $c=1$ means a white stone. The next $m$ lines each contain three integers $u,v,w$, meaning there is an edge connecting $u$ and $v$ with weight $w$.

Output one line with one integer, the required answer.

### Sample 1 Explanation For the first sample, you can choose vertex $3$, then move the black stone on vertex $1$ to vertex $2$, and move the black stone on vertex $2$ to vertex $3$. In this way, the two stones are on vertices directly connected by an edge of weight $2$, so the produced points are $2$. ### Subtasks For all testdata, it is guaranteed that $3 \leq n \leq 100$, $n-1 \leq m \leq \frac{n(n-1)}{2}$, $1 \leq k \leq n-1$, $0 \leq w_i \leq 10^5$.  Translated by ChatGPT 5