[SGU534] 计算机网络

题目描述

Berland 最好的物理数学学校的计算机网络是一棵树，共有 $n$ 台计算机和 $n-1$ 条网线。第 $i$ 条网线连接计算机 $a_i,b_i$，数据包经过该网线的平均传输时间为 $t_i$。

两台计算机之间的传输时间等于它们之间唯一路径上所有网线传输时间之和。整张网络中，两台计算机之间传输时间的最大值称为网络的直径。

现在可以更换若干条网线。更换第 $i$ 条网线需要花费 $p_i$，更换后这条网线仍连接原来的两个端点，但其传输时间变为 $0$。

请选择若干条网线进行更换，使得新网络的直径严格小于原网络的直径，并使更换网线的总花费最小。

请输出这个最小总花费。

输入格式

第一行一个整数 $n$，表示计算机数量，$2\le n\le 10^5$。

接下来 $n-1$ 行，每行四个整数 $a_i,b_i,t_i,p_i$，表示第 $i$ 条网线：

• $1\le a_i,b_i\le n$；
• $1\le t_i,p_i\le 10^4$。

输入保证所有网线构成一棵树。

输出格式

输出一行一个整数，表示使网络直径严格减小所需的最小总花费。

样例 1

样例输入

4
1 2 3 3
1 3 8 33
1 4 3 7

样例输出

10

样例 2

样例输入

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

样例输出

2