Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
G. Cow and Exercise

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputFarmer John is obsessed with making Bessie exercise more!

Bessie is out grazing on the farm, which consists of $$$n$$$ fields connected by $$$m$$$ directed roads. Each road takes some time $$$w_i$$$ to cross. She is currently at field $$$1$$$ and will return to her home at field $$$n$$$ at the end of the day.

Farmer John has plans to increase the time it takes to cross certain roads. He can increase the time it takes to cross each road by a nonnegative amount, but the total increase cannot exceed $$$x_i$$$ for the $$$i$$$-th plan.

Determine the maximum he can make the shortest path from $$$1$$$ to $$$n$$$ for each of the $$$q$$$ independent plans.

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}$$$.

Example

Input

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

Output

3.0000000000 4.0000000000 4.5000000000 5.0000000000 5.5000000000

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/09/2021 05:18:04 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|