Please submit only Python source code $(.$py or $.$py$3$ extensions only$).$

$1.$ Finding the cheapest and easiest trip in Bustralia $20$ Marks

Bustralia is famous for its busses and for your forthcoming holiday there you want

to plan a number of bus journeys between towns. You are budget conscious so want

to find the lowest cost trips but you find transferring between busses stressful. To

try to take the stress factor into account, you decide that you will make a trip with

more transfers than the absolute minimum required only if each additional transfer

will save you a reasonable amount of money, and that you will make at most a fixed

number of transfers per journey. Where two journeys are equal when compared based

on cost and the number of transfers, choose the one with the lowest fare.

Bustralia very usefully publishes a network planners for each region showing all bus

routes between towns and their associated costs.

Your task is to write a program that finds the lowest cost fare between two towns

within a region accounting for the required saving to make a transfer of $t per transfer

and allow yourself no more than k transfers per journey.

Input format: A sequence of one or more input problems is taken from the standard

input $($sys$.$stdin$).$ The bus network for a region is represented by a weighted digraph

in adjaceny lists format with positive integer valued weights and node names from $0$

to n $1$ representing the towns.

Each problem starts with two lines. The first line is contains a single integer n $($at

least $2)$ representing the order of the digraph. The next line has $4$ integers separated

by whitespace:

s x t k

where s is the start town for the journey, x is the end town for the journey, t is

the required saving to make a transfer, and k is the maximum number of transfers

allowed for the journey. Then n lines follow that are the n weighted adjacency lists

of the digraph.

The input is be terminated by a line consisting of one zero $(0).$ This line should not

be processed.

The following example input consists of two problems. The first problem has a region

with $4$ towns, the intended journey from town $0$ to town $2,$ any extra transfer is made

only if it saves at least $$25,$ and a maximum number of transfers set at $1.$

The second problem has $3$ towns, the intended journey from town $0$ to town $1,$ any

extra transfer is made only if it saves at least $$20,$ and a maximum number of transfers

set at $1.$

$4$

$02251$

$1452100320$

$2353100$

$090$

$290$

$3$

$01201$

$180230$

$070$

$130$

$0$

Output format:

Output is simply a sequence of lines, one for each input problem. Each line con$-$

tains an integer showing the cost of the best priced journey taking into account the

constraints. If the intended journey is not possible, output $0$ for that problem.

The output for the sample input is as follows.

$100$

$60$