#P4738. 汽水
汽水
题目描述
牛牛来到一个盛产汽水的国度旅行。这个国度的 个城市由 条双向道路连接,任意两个城市之间都存在路径。经过第 条道路时,牛牛会喝 单位的汽水。
牛牛可以选择任意城市作为起点,每天沿一条道路到达一个未去过的城市,至少走一天。他想使每天饮用的汽水量的平均值尽可能接近给定的 。若所选旅行经过 条道路,总共喝了 单位的汽水,求 的最小值。
输入格式
第一行包含两个整数 。城市编号为 至 。
接下来 行,每行包含三个整数 ,表示城市 之间有一条道路,经过时喝 单位的汽水。同一行相邻的整数用一个空格隔开。
输出格式
输出一个整数,表示 的最小值向下取整后的结果。
样例 #1
样例输入 #1
5 21
1 2 9
1 3 27
1 4 3
1 5 12
样例输出 #1
1
数据范围
,。旅行至少经过一条道路。