무지개길 경주

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

경주는 축제 텐트에서 시작한다. 경주의 목표는 모든 색의 분필을 묻히고 텐트로 돌아오는 것이다. Marcy가 모든 색을 얻고 텐트로 돌아오기 위해 이동해야 하는 최단 거리를 구하자.

그림 J.1: 왼쪽 그림은 예제 입력 1을, 오른쪽 그림은 예제 입력 2를 나타낸다. 삼각형이 축제 텐트이다.

첫째 줄에 축제의 놀이 장소 수 $n$ ($7 \leq n \leq 7^3$)과 놀이 장소를 잇는 거리 수 $m$ ($7 \leq m \leq 7^4$)이 주어진다. 놀이 장소는 $1, \dots , n$으로 번호가 매겨지며 축제 텐트는 장소 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가 모든 색을 얻고 축제 텐트로 돌아오기 위해 이동해야 하는 최단 거리를 출력한다.