题目描述

现在，保密成为一个很重要也很困难的问题。如果没有做好，后果是严重的。比如，有个人没有自己去修电脑，又没有拆硬盘，后来的事大家都知道了。

当然，对保密最需求的当然是军方，其次才是像那个人。为了应付现在天上飞来飞去的卫星，军事基地一般都会建造在地下。

某 K 国的军事基地是这样子的：地面上两排大天井共 $n_1$ 个作为出入口，内部是许多除可以共享出入口外互不连通的空腔，每个空腔有且只有两个出入口，并且这两个出入口不会在同一排。为了方便起见，两排出入口分别编号为 $1, 3, 5, \dots$ 和 $2, 4, 6, \dots$ 并且最大的编号为 $n_1$。

虽然上面扯了那么多关于保密的东西，但是其实解密也是一件很纠结的事情。但其实最简单直接暴力无脑的解密方法就是找个人去看看…

我们有很牛 X 的特种部队，只需要派出一支特种部队到 K 国基地的某个出入口，那么和这个出入口直接相连的所有空腔都可以被探索，但也只有这些空腔可以被这支部队探索。现在有足够多的特种部队可以供你调遣，你必须使用他们调查完所有的 K 国基地内的空腔。

当然，你的基地离 K 国基地不会太近，周边的地图将会给你，表示为 $n$ 个检查点和 $m$ 条连接这些点的道路，其中点 $1$ 到点 $n_1$ 就是 K 国基地的出入口，点 $n$ 是你的部队的出发点。对每条道路，有不同的通行时间 $t$ 和安全系数 $s$ 。因为情报部门只对单向的道路安全系数进行了评估，所以这些道路只允许单向通行，并且不会存在环。

一支特种部队从你的基地出发，通过某条路径，到达某个 K 国基地出入口，此时这支部队的危险性表示为总时间和这条路径经过的所有道路的安全系数和的比值。整个行动的危险性表示为你派出的所有部队的危险性之和。你需要使这个值最小的情况下探索整个 K 国基地。

快点完成这个任务，在 K 国的叫兽宣布你是 K 国人之前。

输入格式

第一行 2 个正整数 $n, m$ 表示整个地区地图上的检查点和道路数。

下面 $m$ 行，每行 4 个正整数 $a, b, t, s$ 表示一条从 $a$ 到 $b$ 的道路需时为 $t$，安全系数为 $s$。

接下来 1 行 2 个正整数 $m_1$ 和 $n_1$, $m_1$ 表示 K 国基地空腔的个数，$n_1$ 表示 K 国基地出入口的个数。

再接下来 $m_1$ 行，每行 2 个正整数 $u, v$，表示每个空腔的 $2$ 个出入口。

输出格式

一行，最小的危险性，保留一位小数。或者输出 -1 表示此任务不可能完成。

5 5
5 1 10 1
5 1 10 1
5 2 9 1
5 3 7 1
5 4 8 1
4 4
1 2
1 4
3 2
3 4

17.0

提示

• 对 $30\%$ 的数据，$n \leq 30$；
• 对 $60\%$ 的数据，$n \leq 300$；
• 另外 $40\%$ 的数据 $n_1 \leq 20$。
• 对于 $100\%$ 的数据，$4 \leq n \leq 700$，$m \leq 100000$，$a, b \leq n$，$1 \leq t, s \leq 10$，$m_1 \leq 40000$，$n_1 < \min(n, 161)$，$u, v \leq n_1$，$u$ 是奇数，$v$ 是偶数。