题目描述

给定一颗树，有 $N$ 个点，$N-1$ 条路，道路双向可通行，但两个方向的距离权重可能不同。

请找出一个点作为中心，使得从该中心出发到所有点的距离中的最大值最小。

输出这个最小值。

输入格式

• 第一行：单个整数 $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

12

数据范围

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