There is a country with N cities connected by M bidirectional roads, and you need to build a fire station somewhere. Of course, your problem would be too simple without the following restrictions:

• Firemen should be able to reach any city from fire station by roads only.
  
  
• You want to minimize expected distance from fire station to place of fire. For this purpose, probability of a fire is given to you for every city. Assume that firemen always choose the shortest way to fire.
  
  
• You can place fire station not only in cities but on the roads between them as well. Moreover, sanity regulations of the country forbid placement of a fire station closer than at a distance R from cities. Distances are measured on roads only, so you can place fire station on a road if its length is not less than 2R, and you should not worry about distances to cities not adjacent to the given road. In particular, R=0 means that you are allowed to place a fire station in cities.
  
  

Example of a country with three cities and three roads. Places where you can build fire station are marked with bold line and bold dot.

You are given a complete description of the country. Find the best place for a fire station in it.

The first line of input file contains integer numbers N, M and R (1 ≤ N ≤ 100, 0 ≤ M ≤ N(N-1)/2, 0 ≤ R ≤ 10⁴). Second line contains N integer numbers — probabilities of a fire in each city. Numbers are non-negative integers given in hundredths of percent (that is, sum to 10⁴). Each of the next M lines contains description of one road, namely three integer numbers A_i, B_i and L_i — endpoints of the road and its length in kilometers (1 ≤ A_i < B_i ≤ N, 1 ≤ L_i ≤ 10⁴). There can be at most one road between any two cities.

Output only one number — expected length of a way to fire in kilometers assuming fire station is built optimally. This number should be precise up to 1 meter. If by some reason it is impossible to build fire station that fulfills all the requirements, write to the output file number -1 instead.

sample input	sample output
3 3 20 3000 5000 2000 1 2 40 1 3 50 2 3 30	26.00000

sample input	sample output
3 1 20 3000 5000 2000 1 3 50	-1

In the first example (which corresponds to the picture above) it is optimal to build fire station in the middle of the first road. In the second example it is impossible to build fire station satisfying all the requirements. In particular, any fire station on the map will violate requirement one (since the country is disconnected).