Description

你正在组织一群滑雪者。滑雪者们将前往一座被全天租用的大型雪山。

雪山上有编号为 $1$ 到 $\mathbf{N}$ 的 $\mathbf{N}$ 个休息点，它们通过 $\mathbf{N}-1$ 条滑雪道相连。每条滑雪道从一个休息点出发，直接通向另一个休息点，中途没有其他滑雪道或休息点。滑雪道只能单向通行。

每位滑雪者从山顶休息点（编号 $1$）出发，沿一条滑雪道到达另一个休息点。之后，滑雪者可以继续沿另一条滑雪道前往下一个休息点，以此类推。当滑雪者到达目标休息点时，他们会结束当天的滑雪并前往滑雪小屋享用热可可。目标休息点不能是山顶休息点。但注意，滑雪者的目标休息点可以是零条或多条滑雪道的起点——即滑雪者不一定要用完所有可用滑雪道：他们可以小心地步行下山！对于所有休息点，从山顶休息点出发到达它的滑雪道序列是唯一的。

每条滑雪道每天仅能容纳一定数量的滑雪者，超过后雪道会因积雪过乱而无法使用。此外，滑雪场会根据滑雪者使用的每条滑雪道收取费用或发放奖励。每条滑雪道的价格可能不同，每位滑雪者需支付其使用的每条滑雪道的价格。价格可以是正数、零甚至负数（负数代表测试该滑雪道的奖励）。作为组织者，你需要代表滑雪者支付所有费用并收取所有奖励。注意，若多名滑雪者使用同一条滑雪道，该滑雪道的费用或奖励会被多次计算。你$$支付的总费用减去收取的总奖励即为本次旅行的总支出。支出可能为正、零或负（负支出表示你实际上赚了钱）。

作为组织者，你需要计算能安排到雪山上的最大滑雪者数量，并求出在该最大数量下的最小可能支出。

Input Format

输入第一行给出测试用例数量 $\mathbf{T}$。随后是 $\mathbf{T}$ 个测试用例。每个测试用例的第一行包含一个整数 $\mathbf{N}$，表示雪山上的休息点数量。

接下来的 $\mathbf{N}-1$ 行每行描述一条滑雪道，包含四个整数 $\mathbf{U_i}$、$\mathbf{V_i}$、$\mathbf{S_i}$ 和 $\mathbf{C_i}$，分别表示滑雪道的起点休息点、终点休息点、最大承载滑雪者数量以及每位滑雪者的使用价格。

山顶休息点（滑雪者起点）始终编号为 $1$。

Output Format

对于每个测试用例，输出一行 Case #x: y z，其中 $x$ 为测试用例编号（从 $1$ 开始），$y$ 为最大滑雪者数量，$z$ 为安排 $y$ 名滑雪者（每人至少使用一条滑雪道）的最小支出。

2
4
1 2 2 5
1 3 2 5
3 4 1 -2
7
4 7 2 2
1 3 5 5
1 4 2 -1
3 2 3 -2
3 5 2 -1
3 6 2 2

Case #1: 4 18
Case #2: 7 15

Hint

样例解释

在样例 #1 中，可以安排 $1$ 名滑雪者前往休息点 $4$，$1$ 名前往休息点 $3$，$2$ 名前往休息点 $2$。

在样例 #2 中，可以安排 $3$ 名滑雪者前往休息点 $2$，$2$ 名前往休息点 $5$，$2$ 名前往休息点 $4$。

注意：测试用例中第一条滑雪道的起点不一定是山顶休息点，且可能存在 $\mathbf{U_i} > \mathbf{V_i}$ 的情况。

数据范围

• 对所有 $i$，满足 $1 \leqslant \mathbf{U_i} \leqslant \mathbf{N}$。
• 对所有 $i$，满足 $2 \leqslant \mathbf{V_i} \leqslant \mathbf{N}$（没有滑雪道以山顶休息点为终点）。
• 对所有 $i$，满足 $\mathbf{U_i} \neq \mathbf{V_i}$。
• 对所有 $i$，满足 $1 \leqslant \mathbf{S_i} \leqslant 10^5$。
• 对所有 $i$，满足 $-10^5 \leqslant \mathbf{C_i} \leqslant 10^5$。
• 对所有休息点 $r$，从山顶休息点到 $r$ 的滑雪道序列唯一。

测试集 1（10 分，可见判定）

• $1 \leqslant \mathbf{T} \leqslant 100$。
• $2 \leqslant \mathbf{N} \leqslant 1000$。

测试集 2（22 分，隐藏判定）

• $\mathbf{T} = 17$。
• $2 \leqslant \mathbf{N} \leqslant 10^5$。

翻译由 DeepSeek V3 完成