bee 1529 - Max, the Mad

In the year 2042, after the emergence of malevolent Union of Independent Republics (URI), humanity was faced with a huge lack of resources. Water and gasoline have become assets very valuable, with much of the technology was lost after URI taking the world power.

You are part of a resistance group that aims to take away the power of the URI. Max, the hero of the resistance, must perform various missions involving car trips between cities. There are gas stations in each city, despite the high prices. As financial resources to the resistence are limited, you have been asked to write a program that calculates what the minimum amount of credits required to complete each one of the Max missions.

Input

The input consists of several test cases. Each test case is started by three integers N, M and T, (1 ≤ N ≤ 10, 1 ≤ M ≤ 20, 1 ≤ T ≤ 50) corresponding to the number of cities along the route, the number of roads and capacity of the car Max liters tank. The input ends when N = M = T = 0.

The following M lines describe the bonds between the cities. Each line contains the integers A, B and C, (1 ≤ C ≤ 1000) indicating the existence of a route (roundtrip) between cities A and B, with a consumption of C liter of gasoline. Due to the poor state of the roads, it is possible that certain cities are inaccessible. There is more of a direct route between any pair of cities.

The next N lines describe the cost in credits from the union per liter of petrol in each city. The first line describes the cost of city gas in the first, the second line depicts the cost of the second city, and so on.

Output

For each test case, your program should print a line containing the lowest possible cost to travel from town 1 to town N. If it is not possible to travel between cities, print -1.

Sample Input	Sample Output
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

Sample Input

Sample Output

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

-1