465. Fire Station Building

Time limit per test: 0.5 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

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:

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 ≤ MN(N-1)/2, 0 ≤ R ≤ 104). 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 104). Each of the next M lines contains description of one road, namely three integer numbers AiBi and Li — endpoints of the road and its length in kilometers (1 ≤ Ai < BiN, 1 ≤ Li ≤ 104). 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

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

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).

Online Contester Team © 2002 - 2010. All rights reserved.