旅游

题号：NC249075
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 有 $n$ 个城市， $m$ 条连接两个城市的双向道路，每条道路有个损坏值 $a_i$ ，牛牛手里有 $c$ 元，进行第 $k$ 次修复道路操作时需要 $k\times a_i$ 元。
$\hspace{15pt}$ 国家愿意修复损坏值 $\le p$ 的道路，牛牛不需要再花钱修国家帮忙修的路。
$\hspace{15pt}$ 牛牛可以自行决定修复哪些道路以及修复它们的顺序。问 $p$ 至少为多少，牛牛才能用不超过 $c$ 元的总花费使得任意两座城市间可以通过修好的道路互相到达。如果国家不需要修复任何道路，输出 $0$ 。

输入描述:

第一行三个正整数 。
此后  行，第  行输入三个正整数 ，表示第  条边连接城市  和城市 ，损坏值为 。保证无自环，图连通；但是可能存在重边。

输出描述:

在一行上输出一个整数，表示完成目标所需  的最小值。

示例1

输入

复制

输出

复制

说明

当  时，国家免费修复了连接城市  和  的道路。为使所有城市连通，牛牛可以进行如下操作：
修复连接  的道路，花费  元；
修复连接  的道路，花费  元。
共花费  元，能达成目标。

备注:

本题已于下方时间节点更新，请注意题解时效性：
1. 2025-11-19 优化题面文本与格式；修正样例解释笔误。