# Problem D

Random Route

Where do you want to go today, and how do you want to get there? You decide to choose the answer to both questions at random.

You will be given a list of roads. Each road connects one city to another city (all roads are one-way), and each road takes a certain amount of time to drive. You will also be given a starting city. Consider all cities that you’re able to drive to, not including your starting city, and choose one of them at random with uniform probability to be your destination. Now consider every fastest route from your starting city to your destination city, and choose one of these routes at random with uniform probability. This will be the route on which you end up driving.

For each road in the input, your program must output the probability that you will end up driving on that road, given the behavior outlined above.

## Input

The first line of input gives the number of cases,
$N$ ($1 \leq N \leq 100$). $N$ test cases follow. Each case
begins with a line formatted as `num_roads
starting_city` ($1 \leq
\mathtt{num\_ roads} \leq 50$). This will be followed by
`num_roads` lines, each formatted as
`city1 city2 time`. Each line
represents a one-way road that starts at `city1` and ends at `city2`, and takes `time`
hours to drive. All cities will be formatted as strings
consisting of only lowercase letters and underscores. For each
road, `city1` will not be equal to
`city2`, and `time` will be an integer between $1$ and $100\, 000$, inclusive. The starting
city is guaranteed to appear as `city1`
on at least one road; therefore, there will always be at least
one possible destination (and at least one shortest route to
that destination).

## Output

For each test case, output one line containing “`Case #$x$:`
” followed by the probability that you will drive on each road,
in the same order that the roads were listed in the input.
Probabilities should be space separated and formatted so there
are exactly seven digits after the decimal point. Each
probability must be within a distance of $10^{-6}$ from the correct answer to
be judged as correct.

Sample Input 1 | Sample Output 1 |
---|---|

1 5 san_francisco san_francisco los_angeles 6 los_angeles san_diego 2 san_francisco san_diego 8 los_angeles san_diego 2 san_francisco los_angeles 6 |
Case #1: 0.4500000 0.2000000 0.1000000 0.2000000 0.4500000 |