Problem Description

Xiao K is a chess player who, after growing tired of traditional Go, has invented a new form of the game.

The new Go is a single-player game. The game board is an undirected connected graph containing $n$ vertices and $m$ edges, with no duplicate edges or self-loops. Each edge has a weight, with the $i$-th edge having a weight of $w_i$.

At the start of the game, each vertex may have a black piece, a white piece, or no piece at all. At least one vertex has no piece. The player then needs to perform several operations. Each operation is as follows:

First, select a vertex $u$ that has no piece on it. It can be shown that under the data range of the problem, such a vertex always exists.

Next, for each piece located at vertex $v$, the player must choose any simple path from $v$ to $u$ and move the piece along this simple path by one step. Formally, a simple path is a sequence of vertices $\{p_1, p_2, \ldots, p_k\}$ such that $p_1 = v$, $p_k = u$, $p_1, p_2, \ldots, p_k$ are distinct, and there is an edge between $p_i$ and $p_{i+1}$. After the operation, the piece will be moved to vertex $p_2$.

It should be noted that although each vertex has at most one piece at the start of the game, after several operations, multiple pieces may be on the same vertex. For different pieces on the same vertex, the simple path chosen during an operation can be different.

The player can perform any number of operations (including zero) and then count the points, i.e., settle the game score. For each pair of pieces of different colors, if they are located at vertices connected by an edge with weight $w$, they are said to surround this edge, which earns the player $w$ points. The points a player earns is the sum of the points generated by all pairs of pieces.

Now, Xiao K has given you the initial board of the game. Please help him find the maximum possible points that can be obtained on this board.

Input Format

The input consists of $m+k+1$ lines.

The first line contains three integers $n, m, k$, representing the number of vertices, edges, and pieces, respectively.

The next $k$ lines each contain two integers $x, c$, indicating that there is a piece of color $c$ on vertex $x$. Here, $c=0$ represents a black piece, and $c=1$ represents a white piece.

The next $m$ lines each contain three integers $u, v, w$, indicating that there is an edge with weight $w$ connecting vertices $u$ and $v$.

Output Format

Output a single integer, which is the answer to the problem.

Sample Input and Output

Input Sample #1

3 2 2
1 0
2 1
1 2 1
2 3 2

Output Sample #1

2

Input Sample #2

4 4 3
1 1
2 1
3 0
1 2 1
2 3 1
3 4 1
4 1 3

Output Sample #2

3

Input Sample #3

See the file in the contestant directory under alphago/alphago3.in and alphago/alphago3.ans.

Output Sample #3

See the file in the contestant directory under alphago/alphago3.in and alphago/alphago3.ans.

Input Sample #4

See the file in the contestant directory under alphago/alphago4.in and alphago/alphago4.ans.

Output Sample #4

See the file in the contestant directory under alphago/alphago4.in and alphago/alphago4.ans.

Input Sample #5

See the file in the contestant directory under alphago/alphago5.in and alphago/alphago5.ans.

Output Sample #5

See the file in the contestant directory under alphago/alphago5.in and alphago/alphago5.ans.

Notes

Sample 1 Explanation

For the first sample, you can select vertex $3$, then move the black piece from vertex $1$ to vertex $2$, and the white piece from vertex $2$ to vertex $3$. This way, the two pieces are located at vertices connected by an edge with a weight of $2$, yielding $2$ points.

Subtasks

For all test data, 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$, and $0 \leq w_i \leq 10^5$.

见题面 Input 部分

见题面 Output 部分