SP4483 MROADS - Roads Repair

一个国家的交通网络由 $N$ 个城市（编号为 1 到 $N$）和 $N-1$ 条道路连接而成。每对不同城市之间，都有一个唯一的路径。 因为多年的懒于维护，这些道路已相当破损。对于每条道路，我们知道两个时间：$A$ 和 $B$。其中，整数 $A$ 代表当前通过这条道路所需的时间（单位为秒），整数 $B$ 代表如若完全修复，这条道路所需的最短时间（也以秒为单位）。 我们计划投资一定的金额来修复这些道路。对于每一条特定道路，修复程度将与投入的资金成正比。每投入一欧元，这条道路的通行时间将减少一秒（对每条道路的投资额必须是整数）。不过，即使用再多资金也不能将通行时间减少到小于最短时间 $B$。 现给定一个固定的总资金，我们需要合理分配到各条道路上，使得从城市 1 到最远城市的通行时间（在所有道路修复后）尽量小。 请编写一个程序，求出这个最小可能的时间。

第一行输入包含两个整数 $N$ 和 $K$，其中 $2 \leq N \leq 10^5$，$0 \leq K \leq 10^9$。 接下来的 $N-1$ 行中，每行包含四个整数 $X$、$Y$、$A$ 和 $B$，表示城市 $X$ 与城市 $Y$ 之间有一条道路，当前通过这条道路需时 $A$ 秒，而修复后的最短时间是 $B$ 秒。其中 $1 \leq B \leq A \leq 10^9$。

输出仅需一行，表示任务要求的最短时间。 **本翻译由 AI 自动生成**