Harry el Hámster#9885
El hámster Harry vive en una enorme jaula para hámsters. Dentro de la jaula hay esferas de plástico, conectadas por tubos de hámster unidireccionales de diferente longitud. Ahora mismo Harry se encuentra en la esfera , y su cama está en la esfera .
Harry es un hámster sencillo, y los dos hemisferios de su cerebro no se llevan muy bien entre sí: cada uno tiene sus propias ideas. El hemisferio izquierdo, que suele estar activo cuando Harry corre en la rueda, quiere correr todo el tiempo posible. El hemisferio derecho, que en general rara vez está activo, quiere acostarse a dormir lo antes posible. Juntos, los hemisferios guían a Harry a través del laberinto de tubos, decidiendo en cada esfera por cuál tubo saliente moverse a continuación.
Tomar una decisión es muy agotador, por lo que después de cada decisión el hemisferio necesita descansar un poco, y no puede tomar dos decisiones seguidas. Por eso los hemisferios eligen el tubo por turnos, y el primero en mover es el hemisferio izquierdo. Comenzando en la esfera , el hemisferio izquierdo elige un tubo que lleva a Harry a cierta esfera . Allí el hemisferio izquierdo descansa, mientras que el derecho elige el siguiente tubo saliente, y así sucesivamente.
Por extraño que parezca, ambos hemisferios conocen toda la jaula y pueden planificar con tanta anticipación como quieran. ¿En cuánto tiempo llegará Harry a su cama, si ambos hemisferios actúan de manera óptima? Se garantiza que de cada esfera sale al menos un tubo, excepto de la esfera con la cama de Harry, de la cual no sale ninguno (allí Harry puede descansar tranquilamente). Ningún tubo conecta una esfera consigo misma, pero puede haber varios tubos que van de una esfera a otra.
En la primera línea se dan cuatro números enteros: la cantidad de esferas de plástico n~(1 \le n \le 10^5), la cantidad de tubos m~(0 \le m \le 2 \cdot 10^5), así como las esferas y t~(0 \le s, t < n), en las que se encuentran Harry y su cama.
Cada una de las siguientes líneas contiene tres números enteros que describen un tubo: la esfera a_i~(0 \le a_i < n) en la que comienza el tubo, la esfera b_i~(0 \le b_i < n) en la que termina, y el tiempo w_i~(1 \le w_i \le 10^4) necesario para recorrerlo. Por cada tubo solo se puede avanzar en una dirección.
Imprima el tiempo en el que Harry llegará a su cama, o la cadena infinity si Harry está condenado a vagar eternamente por los tubos.
Ejemplo 1
Ejemplo 2
Ejemplo 3
Ejemplo 4
Ejemplo 5