很久以前，在一个遥远的王国里，统治着一位英明的国王。国王决定让他的子民生活得更好，并敦促贵族们进行创新、现代化和纳米技术。贵族们思考了一番，想出了一个管道方案。他们的农奴生产的纳米管并没有“那么”好，所以他们用木管代替了它们。

木制管道将王国的所有 $N$ 个城镇连接成一个单一的网络，使得你可以沿着管道从任意一个城镇走到另一个城镇。该管道网络由 $N - 1$ 条管道组成。每条输水管道直接连接两个城镇，没有任何分支。每条管道的容量是已知的，即单位时间内可以通过该管道的最大水量。

多年后，这位英明国王的统治结束了。他的儿子将国家推向了资本主义道路。他的孙子继承了一个预算空空、债务累累的现代国家。这些年来，管道一直处于闲置状态。但它没有发生任何损坏，因为它在建造时就被设计为永久耐用！好吧，这并不完全准确。确实发生了一些事情——为了防万一，部分管道被私有化了。最后，城镇 $U$ 发生了旱灾，孙子想起了祖父的计划——他们将通过管道抽水并供应城镇 $U$。

除了 $U$ 以外，所有城镇都可以分为两类：终端城镇和中间城镇。如果一个城镇有一条管道通往比它距离 $U$ 更远的城镇（距离沿管道计算），则该城镇为中间城镇。所有其他城镇都被视为终端城镇。允许从所有终端城镇提取任意数量的水，并通过管道将其泵入城镇 $U$。不能从中间城镇提取水。

不幸的是，有一些卑劣的人想从这场灾难中获利，并对通过他们管辖的管道段抽水收取费用。由于私有产权、自由市场等原因，国王对此无能为力。为了对抗这些吸血鬼，忠诚的公民宣布，他们很荣幸能提供自己的管道段来向城镇 $U$ 输送水，甚至愿意为此付钱。因此，对于每条管道，我们知道每单位流量的水流经它的成本，且这个成本可以是负数。

国王破产了，预算中没有钱。请帮他制定一个计划，向 $U$ 供应尽可能多的水，但要确保不需要额外的资金（即总成本不超过 0）。

输入格式

输入第一行包含一个整数 $N$ —— 城镇的数量（$2 \le N \le 200\,000$）。

接下来的 $N - 1$ 行每行描述一条管道。每条管道由四个整数描述：$a$ —— 管道起点的城镇编号，$b$ —— 管道终点的城镇编号，$M_{ab}$ —— 管道的容量（单位时间内流过的体积单位），$C_{ab}$ —— 通过该管道泵送单位体积水的成本（$1 \le a \neq b \le N$，$1 \le M_{ab} \le 10^6$，$|C_{ab}| \le 10^7$）。

保证可以通过管道从任意城镇到达其他任意城镇。城镇 $U$ 的编号为 1。

输出格式

输出一个实数 $F$ —— 单位时间内可以泵入城镇 $U$ 的最大水量。绝对误差或相对误差不能超过 $10^{-12}$。

样例

输入样例 1

2
1 2 10 -15

输出样例 1

10

输入样例 2

6
1 3 5 -4
1 2 14 2
4 2 6 -1
5 2 3 5
6 2 6 1

输出样例 2

15.666666666666666667

说明

在第一个样例中，有一条成本为负的管道。你可以将其使用到最大容量，并且还能赚一些钱。

在第二个样例中，最优方案如下。从 1 到 3 泵送 5 单位的水，赚取 20 个金币的利润。从 1 到 2 泵送 $10 \frac{2}{3}$ 单位的水，这将花费我们 $21 \frac{1}{3}$ 个金币。在这些水中，有 6 单位的水从 2 泵送到 4，获得 6 个金币的利润；剩余的 $4 \frac{2}{3}$ 单位的水从 2 泵送到 6，这将花费我们 $4 \frac{2}{3}$ 个金币。