# Problem L

Rainbow Road Race

Marcy is attending Pride Fest and has signed up to participate in the Rainbow Road Race. On each street, there are volunteers who have colored chalk powder. As contestants walk along a street, volunteers throw chalk onto the contestants. The chalk thrown on each street is one of the seven colors of the rainbow (Red, Orange, Yellow, Green, Blue, Indigo, Violet). Once a person starts walking along a street, they must walk to the end of that street.

The race starts at the *Festival Tent*.
The goal of the race is to get covered by chalk of every color
and come back to the tent. Help Marcy determine the shortest
distance she has to travel to get every color and make it back
to the tent.

## Input

The first line of input contains two integers $n$ ($7 \leq n \leq 7^3$), which is the number of fun locations at the festival, and $m$ ($7 \leq m \leq 7^4$), which is the number of streets connecting the fun locations. The fun locations are numbered $1, \dots , n$ and the Festival Tent is location $1$.

The next $m$ lines
describe the streets. Each of these lines contains three
integers $\ell _1$,
$\ell
_2$ ($1 \leq \ell _1
< \ell _2 \leq n$) and $d$ ($1 \leq d \leq 7^5$), followed by a
single character $c$ ($c$ is one of `R`, `O`, `Y`, `G`, `B`, `I`, `V`). This specifies that this street connects
locations $\ell _1$ and
$\ell _2$, is $d$ meters long and the chalk thrown
is color $c$.

It is always possible to travel between any pair of fun locations. There is at most one street between any two pairs of locations and each color appears at least once.

## Output

Display the shortest distance Marcy has to travel to get every color and make it back to the Festival Tent.

Sample Input 1 | Sample Output 1 |
---|---|

7 7 1 2 1 R 2 3 1 O 3 4 1 Y 4 5 1 G 5 6 1 B 6 7 1 I 1 7 1 V |
7 |

Sample Input 2 | Sample Output 2 |
---|---|

8 7 1 2 1 R 1 3 1 O 1 4 1 Y 1 5 1 G 1 6 1 B 1 7 1 I 1 8 1 V |
14 |