De aventura por el Amazonas
India Nayons quiere planificar una aventurilla por el Amazonas. A lo largo del río hay una serie de poblados indígenas, cuyos habitantes, al observar el creciente auge del turismo rural, han ideado un sistema de alquiler de canoas. En cada poblado se puede alquilar una canoa, la cual puede devolverse en cualquier otro poblado que esté a favor de la corriente.
Consultando por Internet los costes de alquileres entre poblados, India ha constatado que el coste del alquiler desde un poblado i hasta otro j puede resultar mayor que el coste total de una serie de alquileres más breves. En tal caso, es más rentable devolver la primera canoa en alguna aldea k entre i y j, y seguir camino en una segunda canoa, sin ninguna penalización por cambiar de canoa.
¿Sabrías calcular el coste mínimo de un viaje en canoa desde todos los posibles puntos de partida i hasta todos los posibles puntos de llegada j?
Entrada
La entrada está compuesta por diversos casos de prueba. Cada uno comienza con una línea con el número N de poblados (al menos 2, y no más de 200). A continuación aparece la información sobre los alquileres. Esta consta de N − 1 líneas: la primera tiene N − 1 valores, que representan el coste del alquiler de una canoa para viajar del primer poblado a cada uno de los demás a favor de la corriente; la segunda tiene N − 2 valores, que representan los costes de los alquileres desde el segundo poblado a todos los demás a favor de la corriente (el tercero, el cuarto, etc.); y así hasta que la última línea tiene un único valor que representa el coste del alquiler de una canoa desde el penúltimo poblado al último. Todos los costes son números entre 1 y 1.000.000.
Salida
Para cada caso de prueba se deben escribir N − 1 líneas, con el coste mínimo de cada posible viaje. La primera línea contendrá N − 1 valores, que representarán el coste mínimo de un plan de viaje que comienza en el primer poblado y termina en cada uno de los siguientes a favor de la corriente; la segunda línea contendrá N − 1 valores que representarán los costes mínimos para viajar desde el segundo poblado a todos los demás a favor de la corriente; etc.
Entrada de ejemplo
5 3 10 30 90 5 20 15 10 8 4
Salida de ejemplo
3 8 18 16 5 15 13 10 8 4