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

입력

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

The next $mm$ lines describe the streets. Each of these lines contains three integers ${\mathrm{\ell }}_1\backslash ell\_1$, ${\mathrm{\ell }}_2\backslash ell\_2$ () and $dd$ ($1\le d\le 7^{5}1\; \backslash leq\; d\; \backslash leq\; 7^5$), followed by a single character $cc$ ($cc$ is one of R, O, Y, G, B, I, V). This specifies that this street connects locations ${\mathrm{\ell }}_1\backslash ell\_1$ and ${\mathrm{\ell }}_2\backslash ell\_2$, is $dd$ meters long and the chalk thrown is color $cc$.

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.

출력

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