Maximum Score in New-Style Go

A famous player, K, invented a new single‐player board game, New‑Style Go. The board is an undirected connected graph with n vertices and m edges (no multi‑edges or self‑loops). Each edge i has a weight \(w_i\). Initially, each vertex either contains a black stone, a white stone, or is empty (at least one vertex is empty). The color of a stone never changes.

After the initial setup, the player can perform several operations. In each operation, the following steps occur:

1. Choose an empty vertex \(u\). (It is guaranteed that under the input constraints such a vertex always exists.)
2. For every stone currently on the board (at some vertex \(v\)), choose one simple path from \(v\) to \(u\) and move the stone one step along that path. Formally, if the chosen simple path is \(p_1, p_2, \dots, p_k\) with \(p_1=v\) and \(p_k=u\) (and all \(p_i\) are distinct), then the stone moves from \(v\) to \(p_2\).

Note: Although initially there is at most one stone per vertex, after several operations a vertex can contain multiple stones. In one operation, different stones at the same vertex may choose different simple paths.

After performing an arbitrary number of operations (possibly zero), the player proceeds to count the score. For every edge \((u,v)\) with weight \(w\) that directly connects two vertices which host stones of different colors, we say the edge is "surrounded" and the player gets \(w\) points for that edge – and the total score is the sum over all such edges, counting every pair of stones (if more than one stone resides on a vertex, every pair with a stone on the adjacent vertex is counted separately).

Your task is: Given the initial board, compute the maximum score possible.

Remark on moves: In each operation every stone must move one step along an edge. Therefore, after a fixed number of operations every stone will have moved exactly that many steps. In non‑bipartite graphs (i.e. graphs containing an odd cycle) the moves allow you to reassign stones arbitrarily among vertices. However, if the graph is bipartite (for example, if the board is a tree) then for some parity \(k\) all stones must end in vertices whose side is determined by their starting position. In that case the best you can do is to gather all stones originally from one bipartition on one vertex and those from the other bipartition on an adjacent vertex. Thus, the maximum achievable score is:

\[ \begin{cases} w_{\max}\times\Bigl((B_X\times W_Y) + (W_X\times B_Y)\Bigr), & \text{if the graph is bipartite},\\[1mm] w_{\max}\times (B_{\text{total}}\times W_{\text{total}}), & \text{if the graph is non-bipartite}, \end{cases} \]

Here, \(w_{\max}\) is the maximum weight of any edge; for a bipartite graph the two parts are \(X\) and \(Y\), and \(B_X\) (resp. \(W_X\)) is the number of black (resp. white) stones originally in part \(X\) and similarly for \(B_Y, W_Y\); while in the non‑bipartite case, all stones can be arbitrarily reassigned so that the maximum pairing is \(B_{\text{total}}\times W_{\text{total}}\).

Input format:

• The first line contains two integers \(n\) and \(m\) (number of vertices and edges).
• The second line is a string of length \(n\). The \(i\)th character represents the initial state of vertex \(i\): 'B' means a black stone, 'W' means a white stone, and '.' means the vertex is empty. It is guaranteed that at least one character is '.'
• Each of the next \(m\) lines contains three integers \(u\), \(v\) and \(w\), indicating an undirected edge between vertices \(u\) and \(v\) with weight \(w\). (Vertices are 1-indexed.)

Output format:

• Output a single integer: the maximum achievable score.

inputFormat

The input begins with two integers \(n\) and \(m\). The next line is a string of length \(n\) consisting only of characters 'B', 'W', and '.', representing the initial configuration of vertices 1 through \(n\). Then \(m\) lines follow, each containing three integers \(u\), \(v\), and \(w\) denoting an undirected edge between vertices \(u\) and \(v\) with weight \(w\).

outputFormat

Output a single integer — the maximum score achievable by performing the operations optimally.

sample

3 2
B.W
1 2 10
2 3 10

0