Love That Only Fails for Me

Kkaengmi is 24 and has never been in a relationship. Refusing to become a great wizard, Kkaengmi decides to use programming skills to build a group-dating app. The app targets university students and is built from data on the roads between universities.

The app offers its users a crush route. A crush route satisfies these three conditions:

1. To satisfy the users' crushes, it consists only of roads that connect a men-majority university with a women-majority university.
2. So that users can meet many different people, it lets them travel from any university to every other university.
3. So that nobody wastes time, the total length of the roads in the route is as small as possible.

For example, if the road data looks like the figure on the left, building the route like the purple lines in the figure on the right satisfies all three conditions.

Using the given road data, find the length of the crush route.

The first line contains the number of schools $N$ and the number of roads $M$. ($2 \le N \le 1\,000$, $1 \le M \le 10\,000$)

The second line contains $N$ space-separated characters. The $i$-th character is M if school $i$ is a men-majority university and W if it is a women-majority university.

Each of the next $M$ lines contains three integers $u$, $v$, and $d$, meaning that school $u$ and school $v$ are connected by a road of length $d$. ($1 \le u, v \le N$, $1 \le d \le 1\,000$)

Print the length of the crush route of Kkaengmi's app. If the allowed roads cannot connect all schools, print -1.