题目描述

给定一个有向图，其中有 $n$ 个顶点和 $m$ 条边。请找出从节点 $1$ 到节点 $n$ 的所有路径中，方差的下确界。

从 $1$ 到 $n$ 的路径定义为边的序列 $\{e_1, e_2, \ldots, e_l\}$，其中 $e_1$ 的起点是 $1$，$e_l$ 的终点是 $n$，$e_i$ 的终点和 $e_{i+1}$ 的起点相同。注意 $e_1, e_2, \ldots, e_l$ 是可重的。一条路径 $p = \{e_1, e_2, \ldots, e_l\}$ 的方差定义为：

$$D(p) = \frac{1}{l} \sum_{i=1}^{l} (w_{e_i} - \overline{w})^2$$

其中，$w_{e_i}$ 是边 $e_i$ 的权重，$\overline{w} = \frac{1}{l} \sum_{i=1}^{l} w_{e_i}$ 是路径中所有边 $e_1, e_2, \ldots, e_l$ 的平均权重。

本题中，下确界的定义在输出格式中给出。

输入格式

第一行包含两个整数 $n$ ($2 \leq n \leq 30$) 和 $m$ ($1 \leq m \leq 200$) 。

接下来的 $m$ 行中，第 $i$ 行包含三个整数 $x_i, y_i, w_i$ ($1 \leq x_i, y_i \leq n, x_i \neq y_i, 0 \leq w_i \leq 20$) 表示从 $x_i$ 到 $y_i$ 有一条权重为 $w_i$ 的有向边。

输出格式

输出一行，包含一个实数，表示从节点 $1$ 到节点 $n$ 的所有路径中方差的下确界。

如果不存在从节点 $1$ 到节点 $n$ 的任何路径，请输出 -1（不带引号）。

你的答案会被认为是正确的，当且仅当其绝对或相对误差不超过 $10^{-9}$。形式化地，假设你的答案是 $b$，设 $\epsilon = \max\{1, b\} \cdot 10^{-9}$，则你的答案被认为是正确的，如果满足以下条件：

• 对于任意从 $1$ 到 $n$ 的路径 $p$，都有 $D(p) > b - \epsilon$;

• 至少存在一条从 $1$ 到 $n$ 的路径 $p_0$，使得 $D(p_0) < b + \epsilon$。

4 4
1 2 3
1 3 4
2 4 5
3 4 7

1.000000000000000