该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

最优装备

题目描述

Z 城市的地下管道系统包含 $n$ 个关键节点和 $n-1$ 条双向管道。系统保证任意两个节点之间有且仅有一条简单路径（即树形结构）。

工程师当前位于节点 $1$，需要前往节点 $n$ 执行任务。必须沿着唯一的路径前进。

每条管道都有一个固定的腐蚀值 $w_i$。为了安全通过，必须在出发前购买一套防护装备。装备有一个等级 $k$（$k$ 为整数，且 $k \ge 1$）。

• 购买等级为 $k$ 的装备，你需要支付 $k$ 枚金币作为基础成本。
• 装备可以减轻腐蚀带来的伤害。当你携带等级为 $k$ 的装备通过一条腐蚀值为 $w$ 的管道时，受到的伤害值为 $\lfloor \frac{w}{k} \rfloor$（即 $w$ 除以 $k$ 下取整）。

任务的总花费定义为“装备等级 $k$ ”与“路径上造成的最大单次伤害”之和

请计算从节点 $1$ 到达节点 $n$ 所需的最小总花费。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 10^5$)，表示节点数量。

接下来 $n-1$ 行，每行包含三个整数 $u, v, w$ ($1 \le u, v \le n, 1 \le w \le 10^{18}$)，表示节点 $u$ 和 $v$ 之间有一条腐蚀值为 $w$ 的管道。

输出格式

输出一个整数，表示最小的总花费。

输入输出样例 #1

输入 #1

5
1 2 10
2 3 50
3 4 5
4 5 100

输出 #1

20

说明/提示

路径为 $1 \to 2 \to 3 \to 4 \to 5$。路径上的腐蚀值集合为 $\{10, 50, 5, 100\}$。最大值为 $100$。

我们需要最小化 $k + \lfloor 100/k \rfloor$。

• $k=1$: $1 + 100 = 101$

• $k=10$: $10 + 10 = 20$

• $k=20$: $20 + 5 = 25$

  最小花费为 20。