El ingenioso Willy
William Francis Sutton, también conocido como el ingenioso Willy, fue un famoso ladrón de bancos de Estados Unidos que cometió más de 100 atracos en las primeras décadas del siglo XX. La cantidad total de dinero robado se estima en unos 2 millones de dólares de la época.
Para la historia ha quedado como un maestro de los disfraces que conseguía embaucar a cualquiera de tal forma que nunca tuvo que disparar una sola bala. De hecho, él mismo aseguró en una entrevista al final de sus días que las armas que usaba nunca iban cargadas, pues alguien podría resultar herido.
Lo que pocos saben es que también era muy metódico planificando sus crímenes. Antes de entrar en un banco establecía perfectamente su plan de huida hasta su guarida, que alcanzaba siempre utilizando el camino más corto hasta ella. Arnold Schuster, un detective aficionado, conocía perfectamente su modus operandi así que cuando sospechaba que Willy iba a actuar ponía vigilancia en todas las calles por las que este podría pasar.
Pero Willy no era tonto. Si al entrar en un banco veía a Arnold merodeando sabía que sus rutas de escape no eran seguras y buscaba la siguiente alternativa más rápida.
Entrada
La entrada está formada por distintos casos de prueba cada uno representando una situación de atraco.
La primera línea de cada caso de prueba tiene dos números, NI (hasta 10.000) y NC (hasta 100.000) representando el número de intersecciones y el número de calles de la ciudad. A continuación aparecen NC líneas con la información de cada calle: dos números (entre 1 y NI) con las intereseciones que unen seguidos de un número que indica el tiempo que se tarda en recorrer esa calle en cualquier sentido (como mucho 10.000).
En cada caso de prueba el banco está situado en la intersección 1 y la guarida de Willy en la NI, y siempre hay al menos un camino desde el banco a la guarida.
Salida
Por cada caso de prueba se escribirá el tiempo que tardará Willy en llegar desde el banco a su guarida si esquiva las calles que podría haber utilizado con su plan original de seguir el camino más corto. Ten en cuenta que lo que debe evitar son las calles pero la ruta alternativa que siga puede pasar por interesecciones por las que también pasaba el plan original.
En caso de no poder llegar a la guarida se escribirá IMPOSIBLE.
Entrada de ejemplo
3 3 1 2 1 2 3 1 1 3 3 3 3 1 2 1 2 3 1 1 3 2
Salida de ejemplo
3 IMPOSIBLE