小 Fabijan 喜欢酒吧和旅行。他希望在他国家的 $N$ 个城镇中各喝一杯咖啡，这些城镇方便地从 $1$ 到 $N$ 编号。城镇之间通过 $(N - 1)$ 条双向道路连接，使得从任意一个城镇出发都可以通过经过某些道路到达另一个城镇。Fabijan 决定按照从城镇 $1$ 到城镇 $N$ 的顺序在每个城镇喝咖啡。因此，他从城镇 $1$ 出发（在那里喝他的第一杯咖啡），然后前往城镇 $2$ 喝下一杯咖啡。在这次旅行中，他可能会经过许多不同的城镇，但他不会在这些城镇停留喝咖啡。在城镇 $2$ 喝完咖啡后，他将继续前往城镇 $3$，依此类推，直到最终到达城镇 $N$，在那里喝完他的最后一杯咖啡。

为了通过某条道路，他需要持有有效的车票。如果持有单次票（价格为 $C_{i1}$ 欧元）或多次票（价格为 $C_{i2}$ 欧元），就可以通过第 $i$ 条道路。对于每条道路，Fabijan 可以选择在每次需要通过该道路时购买单次票，也可以选择只购买一次多次票。

编写一个程序，计算 Fabijan 成功完成旅行所需支付的最少车票费用（单位：欧元）。

输入格式

第一行包含一个整数 $N$（$2 \le N \le 200\,000$）。

接下来的 $(N - 1)$ 行中，第 $i$ 行包含四个整数 $A_i, B_i, C_{i1}, C_{i2}$（$1 \le A_i, B_i \le N$，$1 \le C_{i1} \le C_{i2} \le 100\,000$），表示城镇 $A_i$ 和 $B_i$ 之间有一条道路连接，单次票价格为 $C_{i1}$，多次票价格为 $C_{i2}$。

输出格式

输出一行，表示旅行的最小花费。

子任务

样例

输入样例 1

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

输出样例 1

10

输入样例 2

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

输出样例 2

16

输入样例 3

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

输出样例 3

11

说明

样例 1 说明：

Fabijan 首先从城镇 $1$ 旅行到城镇 $2$，对他来说，购买连接它们的道路的多次票（$5$ 欧元）是最优的。然后他通过城镇 $1$ 从城镇 $2$ 旅行到城镇 $3$。他已经拥有了从 $2$ 到 $1$ 的多次票，并且他购买了一张从城镇 $1$ 到城镇 $3$ 的单次票（$2$ 欧元）。在从城镇 $3$ 到城镇 $4$ 的旅行中，他购买了另一张将他从城镇 $3$ 带回城镇 $2$ 的单次票（$2$ 欧元），之后又购买了一张将他从城镇 $2$ 到城镇 $4$ 的单次票（$1$ 欧元）。总共，他花费了 $5 + 2 + 2 + 1 = 10$ 欧元。