Kenosha, la ciudad más cercana al Granjero Juan tiene ~M~ ~(1 \leq M \leq 14,000)~ carreteras convenientemente numeradas 1..M que conectan ~N~ ~(2 \leq N \leq 300)~ intersecciones convenientemente numeradas 1..N. Ningún par de carreteras conectan el mismo par de intersecciones. Ninguna carretera conecta una intersección con sí misma. El tiempo de recorrido entero ~T_{ij}~ ~(1 \leq T_{ij} \leq 100)~ entre las intersecciones ~i~ y ~j~ es el mismo para ambas direcciones (esto es, ~T_{ij} = T_{ji}~).

Cada intersección tiene un solo semáforo con dos colores: azul o purpura. El color de cada semáforo se alterna periódicamente: azul por cierta duración y luego purpura por otra. Se permite que el tráfico fluya entre dos intersecciones si y sólo si los semáforos en las dos intersecciones son del mismo color en el momento de partir de una intersección a la otra. Los semáforos no tienen que ser necesariamente iguales en todo el camino.

Si un vehículo llega a una intersección exactamente en el momento en que las luces cambian se deben considerar los nuevos colores de semáforos. Se permite que los vehículos esperen en las intersecciones. A usted se le da el mapa de la ciudad que muestra:

• Las tiempos de desplazamiento ~T_{ij}~ para todas las carreteras
• Las duraciones de los dos colores en la intersección i. ~(DB_i (1 \leq DB_I \leq 100)~ para la luz azul y ~DP_i~ ~(1 \leq DP_i \leq 100)~ para la luz purpura.
• El color inicial ~C_i~ del semáforo en la intersección I (una letra 'B' o 'P' representando azul o purpura) y el tiempo restante ~R_i~ ~(1 \leq R_i \leq 100)~ para que este color cambie.l

Encuentre el tiempo mínimo que uno necesita para ir de una fuente dada ~S~ ~(1 \leq S \leq N)~ a un destino dado ~D~ ~(1 \leq D \leq N; D \neq S)~.

Considere el mapa a continuación con cuatro intersecciones y cinco carreteras. GJ quiere ir de la intersección 1 a la intersección 4. El primer semáforo está en azul, el resto está en purpura.

                                    Color Tiempo  Ciclo Ciclo
       4       76         Intersec  Inic   Rest   Azul  Purpura
>>[1B]===[2P]======          1        B     2     16      99
    |   /          \         2        P     6     32      13
  40|  /75          \        3        P     2     87       4
    | /              \       4        P    38     96      49 
  [3P]===============[4P]>>
           77

El tiempo mínimo es 127 utilizando el camino ~1-2-4~.

Inicialmente, el semáforo en la intersección 1 está en azul. Como el semáforo en la intersección 2 está en purpura, el vehículo espera en la intersección 2 segundos luego se desplaza 4 segundos a la intersección 2.

En el tiempo 6, el semáforo en la intersección 2 cambia a azul mientras el semáforo en la intersección 4 tiene 32 segundos más para cambiar a azul. Sin embargo después de 32 segundos, el semáforo en la intersección 2 cambia a purpura y el semáforo en la intersección 4 cambia a azul al mismo tiempo. Por lo tanto el vehículo necesita esperar 13 segundos más para que la intersección 2 cambie a azul entonces los semáforos tienen el mismo color y el vehículo se demora 76 segundos en llegar a la intersección 4.

El tiempo total es ~2+4+32+13+76=127~ segundos.

A continuación hay una representación más gráfica de este plan de viaje:

             1    1    2    2    3    3    4    4    5    5    6    6    7    7    8    8    9    9    0    0    1    1    2    2
   0....5....0....5....0....5....0....5....0....5....0....5....0....5....0....5....0....5....0....5....0....5....0....5....0....5..
   --------------------------------------------------------------------------------------------------------------------------------
J1 BBBPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPBBBBBBBBBBBBBBBBPPPPPPPPPP
J2 PPPPPPBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBPPPPPPPPPPPPPBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBPPPPPPPPPPPPPBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
J3 PPPBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBPPPPBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
J4 PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
FJ 1..>>>2............................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>4

Entrada

• Línea 1: Dos enteros separados por espacio: ~S~ y ~D~.
• Línea 2: Dos enteros separados por espacio: ~N~ y ~M~.
• Líneas 3..N+2: La línea ~i+2~ describe la intersección ~i~ con un carácter y tres enteros (todos separados por espacios): ~C_i, R_i, DB_i~ y ~DP_i~.
• Líneas N+3..N+M+2: La línea ~N+2+k~ describe la carretera ~k~ con tres enteros: ~i, j~ y ~T_ij~.

Salida

Un entero: el tiempo empleado por un camino de tiempo mínimo desde la intersección fuente a la intersección destino. Si no hay camino, dé como salida 0.

Ejemplo de Entrada

1 4
4 5
B 2 16 99
P 6 32 13
P 2 87 4
P 38 96 49
1 2 4
1 3 40
2 3 75
2 4 76
3 4 77

Ejemplo de Salida

127

Adoptado por USACO de la IOI'99