El señor Trujillo es un camionero que transporta diferentes tipos de bienes a través de su país. No obstante, ese país tuvo una serie de problemas sociales, que derivaron en el bloqueo de carreteras. De acuerdo a los contratos que firmó, utilizará el camino más rápido en sus viajes y será multado por cada 24 horas de retraso. En consecuencia, no puede esperar hasta que se resuelvan los conflictos.

Tu trabajo es calcular la multa mínima que el señor Trujillo deberá pagar si es capaz de evadir los bloqueos. Puedes asumir, que sin ningún bloqueo, siempre existirá un camino del origen al destino. Cada carretera es de doble tráfico y toma recorrerla el mismo tiempo de ida o de vuelta. No existirá más de una carretera entre dos ciudades.

Por ejemplo, la figura 1 representa las ciudades y carreteras de un país. Cada carretera está asociada a un tiempo en horas y una etiqueta que indica si está “Bloqueada”. El origen es “La Paz” y el destino es “Santa Cruz”. Si no existen problemas de bloqueo, toma 19 horas viajar esta distancia. Sin embargo, considerando las carreteras bloqueadas, la ruta más rápida toma 45 horas. Este tiempo es 26 horas mayor que el tiempo ideal lo que implica que el conductor deberá pagar una multa.

Tendrás varios casos de prueba. Cada caso comenzará con un par de enteros CR separados por un espacio en una línea. C representa el número de ciudades en el país, y R el número de carreteras que conectan un par de ciudades (2 ≤C, R ≤100). Las siguientes C líneas contendrán los nombres de las ciudades en ningún orden particular, que serán de 12 caracteres como máximo, sin espacios. Las siguientes R líneas representan las carreteras, cada línea tendrá 2 ciudades, las H horas (0,00 ≤H ≤100,00) que toma recorrerla y si está “Bloqueada” o “Expedita”; esta información estará separada por espacios. La última línea tendrá la ciudad de origen, la ciudad de destino y la multa F que debe pagar por cada 24 horas de retraso (0,00 ≤F ≤300,00), separada por espacios. Tanto el tiempo en horas y la multa en pesos, tendrán una precisión de dos dígitos decimales.

La última línea de la entrada contiene “0 0” y no debe ser procesada.

Para cada caso de prueba, debes imprimir una línea con la multa mínima que el señor Trujillo pagará por su retraso si puede evadir los bloqueos. El formato de la multa comenzará con el símbolo $ y tendrá 2 dígitos decimales de precisión. Si no hay una ruta alternativa, debes imprimir el mensaje “Bloqueado”.