题目描述

译自 COCI 2019/2020 Contest #5 T4「Putovanje」

小 Fabijan 喜欢酒吧和旅行。他想要方便地在他的国家内 $N$ 个城市喝酒咖啡。城市编号为 $1\sim N$。城市之间由 $N-1$ 条双向道路连接，从一个城市出发经过一些道路可以到达任意城市。Fabijan 想要按从 $1$ 到 $N$ 的顺序在每个城市喝咖啡。因此，他从 $1$ 号城市出发（在那里他喝了第一杯咖啡），然后他将前往 $2$ 号城市，路途上他不会停在某个城市喝咖啡。在 $2$ 号城市喝完咖啡后，他将前往 $3$ 号城市，然后继续这个过程直到他到达 $N$ 号城市，他会在那里喝最后一杯咖啡。

为了通过某条道路，他需要有通行票。你可以通过第 $i$ 条路当且仅当你有一张价值为 $C_{i1}$ 欧元的单次通行票或者有一张价值 $C_{i2}$ 欧元的多次通行票。对于每条道路，Fabijan 每次需要通过那条道路时都可以决定购买单次通行票，或者他可能会选择购买多次通行票，多次通行票只需要购买一次。

写一个程序计算 Fabijan 至少需要多少欧元才能成功完成他的旅行计划。

输入格式

第一行一个整数 $N$，意义如题目描述；

接下来 $N-1$ 行，每行包含四个整数 $A_i,B_i,C_{i1},C_{i2}$，表示编号为 $A_i$ 和 $B_i$ 的两个城市之间有一条通行票花费为 $C_{i1}$ 和 $C_{i2}$ 的路连接。

输出格式

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

样例

样例输入 1

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

样例输出 1

10

样例说明 1

Fabijan 首先从 $1$ 号城市前往 $2$ 号城市，对于他来说最优的选择是买一张多次通行票（$5$ 欧元），然后他从 $2$ 号城市经 $1$ 号城市到达 $3$ 号城市，他已经有一张从 $2$ 号城市到 $1$ 号城市的多次通行票了，他买了一张 $1$ 城市到 $3$ 城市的单次通行票（$2$ 欧元），然后从 $3$ 号城市到 $4$ 号城市的路上又买了一张 $3$ 号城市到 $1$ 号城市的单次通行票（$2$ 欧元），然后买了一张 $2$ 号城市到 $4$ 号城市的单次通行票（$1$ 欧元），总花费为 $5+2+2+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

数据范围与提示

对于全部数据，$2\le N\le 2\times 10^5,1\le A_i,B_i\le N,1\le C_{i1}\le C_{i2}\le 10^5$。

详细子任务附加限制及分值如下表：