grafos

Ratones en fuga
(tiempo límite: 3 segundos)
Un laboratorio está entrenando ratones para escapar de laberintos, pero no de
cualquier tipo de laberintos. De hecho se trata de aquellos que estáncompuestos por
celdas, cada una de las cuales puede estar conectada con otras. Otra característica es
que cada celda puede varias en cuanto a su superficie, por lo que atravesar diferentes
celdas puedeimplicar diferentes tiempos (en promedio todos los ratones se demoran lo
mismo en atravesar una misma celda). También hay algunos pares de celdas que solo
permiten pasar de una a otra en unadirección específica, no en ambos sentidos.
Supongamos que todos los ratones ya están entrenados y que, al colocarlos en una
celda arbitraria dentro del laberinto, todos encuentran el camino que los guíaa la salida
en el menor tiempo posible. Siendo así pensemos en el siguiente experimento: un ratón
es colocado en cada celda del laberinto e inmediatamente un cronómetro con cuenta
regresiva se ponea correr. Cuando el cronometro pare contamos cuantos ratones han
logrado salir del laberinto. Para esto debemos asumir que no existen “cuellos de botella”
dentro del laberinto, es decir, que todaslas celdas tienen suficiente espacio para
albergar cualquier cantidad de ratones, y que dicha cantidad no afecta el tiempo
promedio de recorrido.
Entrada
La entrada comienza con un valor enteropositivo en una única línea, no mayor a 10 y
que consiste en la cantidad de casos de prueba. Cada caso de prueba comienza con
cuatro líneas especificando el número de celdas N (1 ≤ N ≤ 100), la celdade salida E (1
≤ E ≤ N), el tiempo inicial en segundos del cronómetro T (0 ≤ T ≤ 5000) y el número de
conexiones entre celdas del laberinto M. de columnas M del laberinto. Luego siguen M
líneas,cada una con 3 valores separados entre sí por un espacio en blanco: dos celdas
A y B (las celdas se numeran de 1 a N), y el tiempo t en segundos que se tarda en ir de
A hasta B (1 ≤ t ≤ 50). Nótese...