As long as Binbin loves Sangsang

Binbin misses Sangsang so much. He wants to meet with Sangsang as soon as possible.
Now Binbin downloads a map from ELGOOG.There are N (1<=N<=1,314) cities in the map and these cities are connected by M(0<=M<=13,520) bi-direct roads. Each road has a length L (1<=L<=1,314,520)and is marked using a unique ID, which is a letter fromthe string “LOVE”!
Binbin rides a DONKEY, the donkey is so strange that it has to walk in the following sequence ‘L’->’O’->’V’->’E’->’L’->’O’->’V’->’E’->.... etc.
Can you tell Binbin how far the donkey has to walk in order to meet with Sangsang?
WARNING: Sangsang will feel unhappy if Binbin ride the donkey without a complete”LOVE” string.
Binbin is at node 1 and Sangsang is at node N.

The first line has an integer T(1<=T<=520), indicate how many test cases bellow.
Each test case begins with two integers N, M (N cities marked using an integer from 1…N and M roads).
Then following M lines, each line has four variables“U V L letter”, means that there is a road between city U,V(1<=U,V<=N) with length L and the letter marked is‘L’,’O’,’V’ or ‘E’

For each test case, output a string
1.  “Case ?: Binbin you disappoint Sangsang again, damn it!”
If Binbin failed to meet with Sangsang or the donkey can’t finish a path withthe full “LOVE” string.
2.  “Case ?: Cute Sangsang, Binbin will come with a donkey after travelling ? meters and finding ? LOVE strings at last.”
Of cause, the travel distance should be as short as possible, and at the same time the “LOVE” string should be as long as possible.

2
4 4
1 2 1 L
2 1 1 O
1 3 1 V
3 4 1 E
4 4
1 2 1 L
2 3 1 O
3 4 1 V
4 1 1 E

Case 1: Cute Sangsang, Binbin will come with a donkey after travelling 4 meters and finding 1 LOVE strings at last.
Case 2: Binbin you disappoint Sangsang again, damn it!

FZU

2012 Multi-University Training Contest 7