무지개 도로 경주

Marcy는 Pride Fest에 참가하고 있으며 Rainbow Road Race에 참여하기로 신청했다. 각 거리에는 색 분필 가루를 가진 자원봉사자들이 있다. 참가자들이 거리를 따라 걸을 때, 자원봉사자들은 참가자들에게 분필을 뿌린다. 각 거리에서 뿌리는 분필은 무지개의 일곱 색(빨강, 주황, 노랑, 초록, 파랑, 남색, 보라) 중 하나이다. 한 사람이 어떤 거리를 따라 걷기 시작하면, 그 거리의 끝까지 걸어야 한다.

경주는 Festival Tent에서 시작한다. 경주의 목표는 모든 색의 분필을 뒤집어쓰고 텐트로 돌아오는 것이다. Marcy가 모든 색을 얻고 텐트로 돌아오기 위해 이동해야 하는 최단 거리를 구하도록 도와주자.

왼쪽 그림은 예제 입력 1을, 오른쪽 그림은 예제 입력 2를 나타낸다. 삼각형은 Festival Tent이다.

입력의 첫째 줄에는 두 정수 $n$ ($7 \leq n \leq 7^3$)와 $m$ ($7 \leq m \leq 7^4$)가 주어진다. 전자는 축제의 즐길 거리 장소 수이고, 후자는 즐길 거리 장소들을 연결하는 거리의 수이다. 즐길 거리 장소에는 $1, \dots , n$의 번호가 매겨져 있으며, Festival Tent은 장소 $1$이다.

다음 $m$개의 줄에는 거리들이 주어진다. 각 줄에는 세 정수 $\ell_1$, $\ell_2$ ($1 \leq \ell_1 < \ell_2 \leq n$), $d$ ($1 \leq d \leq 7^5$)와 그 뒤에 한 문자 $c$가 주어진다. ($c$는 R, O, Y, G, B, I, V 중 하나이다.) 이는 이 거리가 장소 $\ell_1$와 $\ell_2$를 연결하고, 길이가 $d$미터이며, 뿌리는 분필의 색이 $c$임을 나타낸다.

어떤 즐길 거리 장소의 쌍 사이도 항상 이동할 수 있다. 어떤 두 장소의 쌍 사이에도 거리는 최대 하나만 있으며, 각 색은 적어도 한 번 등장한다.

Marcy가 모든 색을 얻고 Festival Tent로 돌아오기 위해 이동해야 하는 최단 거리를 출력한다.