P9542 [湖北省选模拟 2023] 棋圣 / alphago

小 K 是一名棋手，厌倦了传统围棋之后，他发明了一种新式围棋。 新式围棋是一种单人游戏。这个游戏的棋盘是一张包含 $n$ 个顶点，$m$ 条边的无向连通图，并且不存在重边和自环。同时，每条边有一个权值，第 $i$ 条边的权值为 $w_i$。 游戏开始时，每个顶点上可能有一颗黑棋或者一颗白棋，或者什么也没有。**至少有一个顶点上没有棋子。** 接下来，玩家需要进行若干次操作。每次的操作形式如下： 首先，选定一个上面没有棋子的顶点 $u$。可以说明，在题目数据范围下，一定存在这样的顶点。 接下来，对于每一颗棋子，若它位于顶点 $v$，则玩家需任选一条从 $v$ 到 $u$ 的**简单路径**，并将这颗棋子沿着这条简单路径移动一步。形式化地，一条简单路径为一个顶点序列 $\{p_1,p_2 \ldots p_k\}$，满足 $p_1 = v$，$p_k = u$ ，$p_1,p_2 \ldots p_k$ **互不相同**，且 $p_i$ 和 $p_{i+1}$ 之间存在一条边。在操作之后，这颗棋子将被移动至顶点 $p_2$。 需要注意的是，虽然在游戏开始时每个顶点上至多存在一颗棋子，但在若干次操作之后一个顶点上可能有多个棋子。对于同一个顶点上的不同棋子，一次操作中选取的简单路径可以不同。 玩家可以在进行任意次操作（可以是 $0$ 次）之后进行**点目**，即结算游戏分数。对于每一对颜色不同的棋子，若它们所在的顶点之间由一条权值为 $w$ 的边直接相连，则称它们**围住了这条边**，会使玩家得到 $w$ 的**目数**。而一个玩家所得到的**目数**即所有棋子对产生的**目数**之和。 现小 K 给了你一张游戏开始时的棋盘，请你帮他求出在这张棋盘上最多可能得到的**目数**。

输入共 $m+k+1$ 行。 第一行三个整数 $n,m,k$，分别表示点和边的数量，以及棋子的数量。 接下来 $k$ 行，每行两个整数 $x,c$，表示顶点 $x$ 上有一颗颜色为 $c$ 的棋子。其中 $c=0$ 表示一颗黑棋，$c=1$ 表示一颗白棋。 接下来 $m$ 行每行三个整数 $u,v,w$，表示图中有一条连接 $u$ 和 $v$ 的权值为 $w$ 的边。

输出一行一个整数，为所求答案。

### 样例 1 解释 对于第一组样例，可以选定顶点 $3$，然后将 $1$ 号点上的黑棋移动到顶点 $2$，将 $2$ 号点的黑棋移动到顶点 $3$，这样两颗棋子所在的顶点之间由一条边权为 $2$ 的边连接，产生的目数为 $2$。 ### 子任务 对于所有测试数据，保证 $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$。