农夫约翰痴迷于让贝西多锻炼!
贝西正在农场里吃草,农场由 $$$n$$$ 田地组成,并通过 $$$m$$$ 定向道路连接。每条路都需要一些时间 $$$w_i$$$ 才能穿过。她目前在 $$$1$$$ 场地,并将在当天结束时返回位于 $$$n$$$ 场地的家。
Farmer John 计划增加穿过某些道路所需的时间。他可以将穿过每条道路所需的时间增加一个非负值,但对于第 $$$i$$$ 个计划,增加的总时间不能超过 $$$x_i$$$。
确定每个 $$$q$$$ 独立计划从 $$$1$$$ 到 $$$n$$$ 的最短路径的最大值。
输入
第一行包含整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 50$$$, $$$1 \le m \le n \cdot (n-1)$$$) — 分别是田地数量和道路数量。
以下 $$$m$$$ 行均包含 $$$3$$$ 整数、$$$u_i$$$、$$$v_i$$$ 和 $$$w_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$1 \le w_i \le 10^6$$$),表示有一条来自田野的道路$$$u_i$$$ 到 $$$v_i$$$ 场,需要 $$$w_i$$$ 时间穿过。
保证存在从字段 $$$1$$$ 到达字段 $$$n$$$ 的方法。保证图不包含自环或平行边。可能有一条从 $$$u$$$ 到 $$$v$$$ 的道路和从 $$$v$$$ 到 $$$u$$$ 的道路。
下一行包含一个整数 $$$q$$$ ($$$1 \le q \le 10^5$$$),即计划数量。
以下 $$$q$$$ 行中的每一行都包含一个整数 $$$x_i$$$,即查询 ($$$0 \le x_i \le 10^5$$$)。
输出
对于每个查询,如果总增量不超过 $$$x_i$$$,则输出 Farmer John 可以做出的最短路径的最大值。
如果您的答案的绝对或相对误差不超过 $$$10^{-6}$$$,则视为正确。
正式来说,让您的答案为 $$$a$$$,陪审团的答案为 $$$b$$$。当且仅当 $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$ 时,您的答案才会被接受。
示例
输入 #1
3 3 1 2 2 2 3 2 1 3 3 5 0 1 2 3 4
输出 #1
3.0000000000 4.0000000000 4.5000000000 5.0000000000 5.5000000000