나만 안되는 연애

깽미는 24살 모태솔로다. 이대로 대마법사가 될 수는 없다고 생각한 깽미는 자신의 프로그래밍 실력으로 미팅 애플리케이션을 만들기로 했다. 이 앱은 대학생을 대상으로 하며, 대학교 사이의 도로 데이터를 모아서 만들었다.

앱은 사용자에게 사심 경로를 제공한다. 사심 경로는 다음 세 조건을 만족한다.

1. 사용자의 사심을 채우기 위해 남초 대학교와 여초 대학교를 잇는 도로로만 이루어진다.
2. 사용자가 다양한 사람과 미팅할 수 있도록 어느 대학교에서 출발하든 모든 대학교로 이동할 수 있다.
3. 시간을 낭비하지 않도록 경로에 포함된 도로 길이의 합이 가장 작아야 한다.

예를 들어 도로 데이터가 왼쪽 그림과 같다면, 오른쪽 그림의 보라색 선처럼 경로를 구성하면 위의 세 조건을 모두 만족한다.

주어진 도로 데이터로 사심 경로의 길이를 구해 보자.

첫째 줄에 학교의 수 $N$과 학교를 잇는 도로의 수 $M$이 주어진다. ($2 \le N \le 1\,000$, $1 \le M \le 10\,000$)

둘째 줄에 $N$개의 문자가 공백으로 구분되어 주어진다. $i$번째 문자는 $i$번 학교가 남초 대학교이면 M, 여초 대학교이면 W이다.

다음 $M$개의 줄에는 각각 세 정수 $u$, $v$, $d$가 주어진다. $u$번 학교와 $v$번 학교가 길이 $d$인 도로로 이어져 있다는 뜻이다. ($1 \le u, v \le N$, $1 \le d \le 1\,000$)

깽미가 만든 앱의 사심 경로 길이를 출력한다. 조건을 만족하는 도로만으로 모든 학교를 연결할 수 없다면 -1을 출력한다.