Cow and Exercise

Description:

Input:

The first line contains integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 50$$$, $$$1 \le m \le n \cdot (n-1)$$$) — the number of fields and number of roads, respectively.

Each of the following $$$m$$$ lines contains $$$3$$$ integers, $$$u_i$$$, $$$v_i$$$, and $$$w_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$1 \le w_i \le 10^6$$$), meaning there is an road from field $$$u_i$$$ to field $$$v_i$$$ that takes $$$w_i$$$ time to cross.

It is guaranteed that there exists a way to get to field $$$n$$$ from field $$$1$$$. It is guaranteed that the graph does not contain self-loops or parallel edges. It is possible to have a road from $$$u$$$ to $$$v$$$ and a road from $$$v$$$ to $$$u$$$.

The next line contains a single integer $$$q$$$ ($$$1 \le q \le 10^5$$$), the number of plans.

Each of the following $$$q$$$ lines contains a single integer $$$x_i$$$, the query ($$$0 \le x_i \le 10^5$$$).

Output:

For each query, output the maximum Farmer John can make the shortest path if the total increase does not exceed $$$x_i$$$.

Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.

Sample Input:

3 3
1 2 2
2 3 2
1 3 3
5
0
1
2
3
4

Sample Output:

3.0000000000
4.0000000000
4.5000000000
5.0000000000
5.5000000000