Problem H
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.

Figure 1: The left picture illustrates Sample Input 1 and the right picture illustrates Sample Input 2. The triangle is the Festival 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.

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

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