题目描述

Rainbow所在学校的网络中有n台计算机,由n-1条电缆相连(即构成树形)。其中第i条电缆连接ai、bi两台计算机,传输时间为ti。当然,网络中任意两台计算机a、b传输数据所需时间就是a到b的路径上所有电缆的传输时间之和。网络的效率关键在于传输时间最长的两台计算机之间传输数据所需要的时间,记为μ。

现在Rainbow所在的学校要对网络进行升级,升级的目标就是减小μ的值。对于第i条电缆,可以花费pi的价钱把它升级为光缆,光缆依然连接ai和bi,不过传输时间快到可以忽略不计!现在学校要选择一些电缆进行升级,使得升级之后μ的值减小的前提下,花费的价钱最少。

输入格式

第一行一个整数n。

接下来n-1行每行四个整数ai、bi、ti、pi。

输出格式

输出升级之后μ的值减小的前提下,花费的最少价钱。

样例输入1

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

样例输出1

10

样例输入2

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

样例输出2

2

数据范围与约定

对于10%的数据,1<=n<=10。

对于40%的数据,1<=n<=1000。

对于100% 的数据,1<=ai,bi<=n<=100000,1<=ti,pi<=10000,计算机和电缆的编号均从1开始。