beecrowd | 1529

Max, o Louco

Por Lucas Hermann Negri, UDESC BR Brazil

Timelimit: 5

No ano de 2042, após o surgimento da malévola União das Repúblicas Independentes (URI), a humanidade se deparou com uma grande escassez de recursos. Água e gasolina se tornaram bens muito valiosos, sendo que boa parte da tecnologia se perdeu após a URI tomar o poder mundial.

Você faz parte de um grupo da resistência, que tem o objetivo de tirar o poder da URI. Max, o herói da resistência, precisa realizar várias missões que envolvem viagens de carro entre cidades. Existem postos de gasolina em cada cidade, apesar dos altos e variados preços. Como os recursos financeiros da resistência são limitados, você foi convocado a escrever um programa que calcule qual a quantidade mínima de créditos da união necessários para completar cada uma das missões de Max.

Entrada

A entrada é composta por vários casos de teste. Casa caso de teste é iniciado por três inteiros, N, M e T, (1 ≤ N ≤ 10, 1 ≤ M ≤ 20, 1 ≤ T ≤ 50) correspondentes ao número de cidades na rota, o número de estradas e a capacidade do tanque do carro de Max, em litros. A entrada acaba quando N = M = T = 0.

As M linhas na sequência descrevem as ligações entre as cidades. Cada linha contém os inteiros A, B e C, (1 ≤ C ≤ 1000) que indicam a existência de uma rota (ida e volta) entre as cidades A e B, com um consumo de C litros de gasolina. Devido ao estado precário das estradas, é possível que determinadas cidades sejam inacessíveis. Não existe mais de uma rota direta entre qualquer par de cidades.

As próximas N linhas descrevem o custo, em créditos da união por litro, da gasolina em cada cidade. A primeira linha descreve o custo da gasolina na primeira cidade, a segunda linha descreve o custo na segunda cidade, e assim por diante.

Saída

Para cada caso de teste, seu programa deverá imprimir uma linha contendo o menor custo possível para viajar da cidade 1 até a cidade N. Caso não for possível viajar entre as cidades, imprima -1.

Exemplo de Entrada Exemplo de Saída

3 2 50
1 2 30
2 3 30
1
1
1
3 1 10
1 2 20
1
1
1
0 0 0

10
-1