题目描述

给定一个树形网络，在该网络中，有 $n$ 个点，$n-1$ 条道路，这些道路都是可以双向通行的，这些道路可以连通所有的点。但注意，每条道路的两个方向可能有不同的距离权重，也就是说，假设一条道路连通了点 $u$ 与点 $v$，则 $u$ 到 $v$ 的距离权重不一定等于 $v$ 到 $u$ 的距离权重。

请找出一个点，作为网络的中心，使得从这个中心出发，到每个点的距离之和达到最小，输出这个最小值。

输入格式

第一行：单个正整数 $n$； 第二行到第 $n$ 行：每行四个整数 $u_i$，$v_i$，$a_i$，$b_i$，表示一条道路连通了 $u_i$ 与 $v_i$，且 $u_i$ 到 $v_i$ 的权重为 $a_i$，$v_i$ 到 $u_i$ 的权重为 $b_i$。

输出格式

单个正整数：表示一个最小的距离之和。

4
1 4 10 2
2 4 9 12
3 4 2 8

20

样例解释 1

以1为中心，距离之和为50 以2为中心，距离之和为37 以3为中心，距离之和为20 以4为中心，距离之和为22

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 300$；
• 对于 $60\%$ 的数据，$1\leq n\leq 5000$；
• 对于 $100\%$ 的数据，$1\leq n\leq 100,000$。
• $1\leq a_i,b_i\leq 1,000,000$。