CF1307G.Cow and Exercise

Farmer 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.

农夫约翰痴迷于让贝茜多锻炼！

贝茜正在农场上吃草。农场由 $n$ 个田地组成，这些田地之间通过 $m$ 条有向道路相连。每条道路的通行时间为 $w_i$。她当前位于第 $1$ 号田地，并将在一天结束时返回位于第 $n$ 号田地的家。

农夫约翰计划增加某些道路的通行时间。他可以将每条道路的通行时间增加一个非负的量，但对于第 $i$ 个计划，所有道路的总增加量不能超过 $x_i$。

对于 $q$ 个相互独立的计划，请分别求出从 $1$ 到 $n$ 的最短路径长度所能达到的最大值。

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

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 50$，$1 \le m \le n \cdot (n-1)$），分别表示田地的数量和道路的数量。

接下来的 $m$ 行中，每行包含三个整数 $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$）。

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

对于每个查询，请输出在总增加量不超过 $x_i$ 的前提下，农夫约翰能使最短路径达到的最大长度。

若你的答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

形式化地，设你的答案为 $a$，评测组的答案为 $b$。当且仅当 $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$ 时，你的答案被接受。