Brain Fry

A programming contest is happening at Rightshift University of Science and Technology in Rightshift city. After the mock contest, the judges become hungry and decide to try local Brain Fry (Mogoj Vuna) with Maskalai roti (bread). But as the brain-fry is very popular dish, it is not guaranteed that if judges go to a restaurant, they will find it there. They learned from the volunteers that there are N restaurants in Rightshift city numbered 1 to N. For the i’th restaurant, the probability to find brain fry is Pi (1 ≤ i ≤ N). But even if they don’t find brain fry at any specific time at a restaurant, they might find it at another time, because the restaurants might refill the brain fry. The probability to find brain fry at restaurant i will remain the same (Pi). The judges are at the university which is denoted by place 0. The Rightshift city can be modeled by an undirected weighted graph where each edge is represented by three numbers u, v and w. Here u and v (0 ≤ u,v ≤ N) are two places (0 is the university and 1 to N are restaurants) and w is the required time needed to travel between u and v. For excessive flyways, place u and v don’t necessarily needs to be physically adjacent. There can be at most one road between any two pair of places. Now, the judges are planning to do something crazy. They decided to spent T times to search for brain fry. They have following strategy:

1. Starting from university (place 0), they will select a random neighbour restaurant, go to that restaurant and follow the step 2. If there is no neighbour restaurant or T time has been elapsed, then they will just quit.
2. At arriving restaurant i, they will check for brain fry here. If they find it (probability of finding it is, Pi) they will eat it instantly (they are really hungry) and will go back to the university (place 0) using shortest distance and stop their search for brain fry.
3. If they don’t find it at restaurant i and T time has been elapsed, they will go back to the university (place 0) using shortest distance. And they will compensate it in the next day’s contest by making fry out of contestants’ brain.
4. Otherwise they will select a random neighbour restaurant again and go to that restaurant and start from step 2 again. If there is no neighbor restaurant from current restaurant, then they will go back to the university (place 0) using shortest distance and start from step 1. Note that, you want to use at most T time but there are some situations where judges have to use more than T time according to the rules above. What is the probability that they will get to eat brain fry? What is the expected time they will take to return to the university? Input First line of the input is TC (≤ 200), then TC test cases follows in next TC lines. First line of each case contains three integer N (1 ≤ N ≤ 250), M (0 ≤ M ≤ min(N(N +1)/2,20000)), T (1 ≤ T ≤ 100). Next line contains N non-negative real numbers, i-th of them is Pi (0 ≤ Pi ≤ 1) means that the probability of finding brain fry in i-th restaurant. Each of the next M lines contains three integer numbers u, v and w (0 ≤ u,v ≤ N and 1 ≤ w ≤ 10). They represent there is a road between place u and v which takes w time to travel. No u, v pair will be given more than once.

2/2 Output For each test case print a line in ‘Case I: P E’ format where I is case number, P is the probability that they will get to eat brain fry and E is the expected time they will take to return to the university. Errors less than 10−5 will be ignored. Sample Input 1 111 0.5 011 Sample Output Case 1: 0.50000 2.00000