J12 习题-1 Kerry 的电缆网络

题目描述

$\text{Kerry}$ 是德国的一位电缆商人。因联合国脱贫计划的邀请，他准备负责在土鲁齐亚埃萨亚克斯乌托斯邦建立电缆网络，以满足这个国家的用电需求。当然，现在土鲁齐亚埃萨亚克斯乌托斯邦没有任何电缆。已知土鲁齐亚埃萨亚克斯乌托斯邦一共有 $n$ 个城镇，已经编号为 $1$ 到 $n$。其中任意两个城镇可能有一条路，也可能没有。如果两个城镇之间有一条路 $p_i$，那么这条路有一个长度 $s_i$ ，则 $\text{Kerry}$ 可以在这两个城市之间建立一条电缆线，电缆线的长度也就是这条路的长度 $s_i$。 现在 $\text{Kerry}$ 准备了 $s$ 长的电缆线，电缆线可以任意拆断，拆断不损失任何电缆线。他需要将土鲁齐亚埃萨亚克斯乌托斯邦所有城镇都能够连入这个电缆网络。那么，$\text{Kerry}$ 能不能使用这s长度的电缆线完成这项工作；如果能够完成，那么 $\text{Kerry}$ 最少耗用多少长度的电缆线呢？

输入格式

第一行一个正实数 $S$； 第二行一个正整数 $n$ ； 接下来一共有 $m$ 行，由每次输入决定，第 $i$ 行有两个整数 $x_i$ , $y_i$ 和一个实数 $s_i$ ，表示编号为 $x_i$ 个村庄和编号为 $y_i$个村庄之间有一条路，路的长度为 $s_i$。 输入保证 $x_i$ 不等于 $y_i$，两个城镇之间不会有两条路。

输出格式

若能够完成（建立这样的电缆网络），则输出（其中代表最少的电缆线长度，保留两位小数）： Need miles of cable 否则输出： Impossible

样例输入

100.0
4
1 2 2.0
1 3 4.2
1 4 6.7
3 4 4.0
2 4 10.0

样例输出

Need 10.20 miles of cable

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据，$1 \leq n,m \leq 100000$。